일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
- 약수 구하기
- BFS
- 자바
- Parcelize
- 2501
- 시뮬레이션
- 백준
- java
- 완전탐색
- hilt
- 백준 퇴사
- 순열
- Android
- 최단경로
- Parcelable
- EditorInfo
- 프로그래머스
- val
- 오르막수
- 조합
- BuildConfig
- Kotlin
- 순수함수
- EditText
- SWEA
- dfs
- 스카이라인 쉬운거
- imeOptions
- 백준 14501
- 지능형 기차2
- Today
- Total
안드 공부를 해볼까?
[Java] SWEA 탈주범 검거 본문
1. 문제분석
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpLlKAQ4DFAUq
7가지의 파이프 모양을 가진 관에 탈주범이 들어갔다.
1시간에 1칸씩 움직일수 있고 주어진 시간이 지났을 때 탈주범이 어디에 있는지 경우의 수를 구하는 문제다.
보자마자 문제에서 BFS하라고 나타내고 있다. 또한 시간마다 어떤 상태인지 알아보는 것이니 모든 큐를 빼고 넣는 방식으로 구현했다.
여기서 볼 점은 파이프를 어떻게 관리하는 하는지다.
필자는 파이프를 종류별로 switch를 했는데 너무 별로였다. 딱 알고리즘 풀다가 이게 맞나? 싶을정도로.
검색해본 결과 다음과 같은 방법을 사용했다.
상하좌우를 인덱스 0, 1, 2, 3이라고 했을 때 각 파이프의 뚫린 곳을 1, 아닌 곳을 0으로 두자
// 상하좌우
static int[][] dirs = {
{0, 0, 0, 0},
{1, 1, 1, 1},
{1, 1, 0, 0},
{0, 0, 1, 1},
{1, 0, 0, 1},
{0, 1, 0, 1},
{0, 1, 1, 0},
{1, 0, 1, 0},
};
// 상하좌우
static int[] dx = {0, 0, -1, 1};
static int[] dy = {-1, 1, 0, 0};
다음과 같이 구현한 상태다
또한, 현재 내가 위로 올라갈려면 위의 파이프는 아래가 뚤려 있어야 한다.
예를 들어보자.
만약 이 파이프에서 시작해서 상하좌우를 움직인다고 하자.
그렇다면 왼쪽으로 간다고 할 때 어떤 파이프만 올 수 있을까?
4번과 5번 1번만 올 수 있다. 즉, 오른쪽이 뚫린 것만 가능한 것이다.
반면에 오른쪽으로 간다고 할 때는 어떤 파이프만 올 수 있을까?
6번, 7번, 1번만 올 수 있다. 즉, 왼쪽이 뚫린 것만 가능하다.
인덱스로 보자면 0 -> 1, 1 -> 0, 2 -> 3, 3 -> 2가 나와야 가능한 것이다.(위로 올라갈려면 아래가 뚫려야 함)
필자는 2로 나눠서 홀수면 1을 빼주고 짝수면 1을 더해줘서 구했다.
2. 구현
import java.util.*;
import java.io.*;
class Point {
int x, y;
Point(int x, int y) {
this.x = x;
this.y = y;
}
}
public class Solution {
static int answer;
static int width, height, m_width, m_height, time;
static int[][] map;
static boolean[][] visited;
// 상하좌우
static int[][] dirs = {
{0, 0, 0, 0},
{1, 1, 1, 1},
{1, 1, 0, 0},
{0, 0, 1, 1},
{1, 0, 0, 1},
{0, 1, 0, 1},
{0, 1, 1, 0},
{1, 0, 1, 0},
};
// 상하좌우
static int[] dx = {0, 0, -1, 1};
static int[] dy = {-1, 1, 0, 0};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int tc = Integer.parseInt(br.readLine());
for (int c = 1; c <= tc; c++) {
StringTokenizer st = new StringTokenizer(br.readLine());
height = Integer.parseInt(st.nextToken());
width = Integer.parseInt(st.nextToken());
m_height = Integer.parseInt(st.nextToken());
m_width = Integer.parseInt(st.nextToken());
time = Integer.parseInt(st.nextToken());
map = new int[height][width];
visited = new boolean[height][width];
answer = 1;
for (int i = 0; i < height; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < width; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
bfs();
System.out.println("#" + c + " " + answer);
}
}
static void bfs() {
Queue<Point> queue = new LinkedList<>();
queue.offer(new Point(m_width, m_height));
visited[m_height][m_width] = true;
for (int t = 1; t < time; t++) {
int size = queue.size();
// 시간 기준이니 모든 큐를 다 빼고 다시 넣고!
for (int i = 0; i < size; i++) {
Point p = queue.poll();
int[] dir = dirs[map[p.y][p.x]];
for (int j = 0; j < 4; j++) {
// 상하좌우로 돌아간다.
if (dir[j] == 0) continue;
int mx = p.x + dx[j];
int my = p.y + dy[j];
// 내꺼랑 연결이 가능한지? -> 상이면 하로 연결, 좌면 우로 연결
int pos = j % 2 == 0 ? j + 1 : j -1;
if (check(mx, my) && dirs[map[my][mx]][pos] == 1) {
visited[my][mx] = true;
queue.offer(new Point(mx, my));
answer++;
}
}
}
}
}
static boolean check(int x, int y) {
if (x < 0 || x >= width || y < 0 || y >= height) return false;
if (visited[y][x] || map[y][x] == 0) return false;
return true;
}
}
check를 통해 인덱스와 방문여부, 0인지를 확인했다.
기존 BFS에서 시뮬레이션이 추가된 문제로 조금 더 생각해보면 풀 수 있을 것이다.
3. 마무리
BFS 응용까지는 알았다. 풀 수도 있는데 내 코드가 너무 더럽다..
그래서 아니 파이프 관리를 어떻게 깔끔하게 하지 하고 봤는데 저런.. 방법이 있더라..
아직 멀었나보다..
'알고리즘 > SWEA' 카테고리의 다른 글
[Java] SWEA 보물상자 비밀번호 (0) | 2022.11.21 |
---|---|
[Java] SWEA 수영장 (0) | 2022.11.19 |
[Java] SWEA 미생물 격리 (0) | 2022.11.19 |
[Java] SWEA 수영대회 결승전 (1) | 2022.11.17 |
[Java] SWEA 보호 필름 (0) | 2022.11.17 |