문제 정의
현재 위치와 시간이 주어지고 시간안에 갈 수 있는 모든 장소의 개수를 계산해야 합니다.
자세한 문제 설명은 문제 바로가기
접근 방법
일단 2차원 배열의 맵이 주어지고 4방으로 탐색해야하기 때문에 기본적으로 BFS 또는 DFS를 모두 사용할 수 있으나 현재 위치에서 한시간마다 한칸씩 주위로 퍼져나가는 형태이기 때문에 DFS보다는 BFS를 사용하는 것이 적합하다고 판단했습니다.
시행 착오
방향 하드코딩
다만 무조건 4방 탐색을 하는 것이 아니라 터널의 종류에 따라 갈 수 있는 방향이 각기 다르므로 종류마다 갈 수 있는 방향을 미리 하드코딩해두고 썼습니다.
이미 한시간이 흐른 상태에서 탐색 시작
또 한가지 헷갈렸던 점은 현재 위치에서 이미 한시간을 쓴 상태이기 때문에 이를 반영해야만 올바른 결과를 얻을 수 있습니다.
DFS로 접근하기
위의 두가지를 잘 반영했다면 BFS로 풀이하는데에는 큰 어려움이 없었으나 DFS로 풀이했을 시 자꾸 다른 결과가 나와서 좀 헤맸습니다.
우선 DFS로 접근할 때에는 방문처리에 주의해야 합니다.
위 그림에서 주황색 칸이 시작위치라고 한다면 초록색 칸까지 도달하는데에는 빨간색 경로와 파란색 경로, 두가지가 존재합니다. 만약 주어진 시간이 7이었고 빨간색 경로로 먼저 DFS 탐색을 시작한 경우 초록색 칸을 방문하는 순간 주어진 시간을 모두 소진했기 때문에 더 이상 탐색하지 못하기에 파란색칸에 도달할 수 없습니다.
이제 파란색 경로로 이동하는 경우 초록색칸이 이미 빨간색 경로로 이동 시 방문 처리 되었기때문에 방문할 수 없어 막히므로 시간이 남았음에도 불구하고 파란색칸을 방문하지 못하는 상황이 발생합니다.
따라서 DFS로 접근할 때에는 반드시 백트래킹을 해주어야 이미 방문한 지점이라도 다른 경로로 다시 방문할 수 있습니다.
그리고 한번이라도 방문한적이 있으면 체크하는 별도의 배열을 따로 만들어 관리해야 나중에 방문한 모든 장소를 카운트할 수 있습니다.
문제 해결
BFS
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Solution_1953_탈주범검거BFS {
// 상 우 하 좌
static final int[] dy4 = {-1, 0, 1, 0};
static final int[] dx4 = {0, 1, 0, -1};
static final int[][] typeTunnel = { // 터널 종류별로 4방향에 대해 뚫려 있는지 여부
{0, 0, 0, 0},
{1, 1, 1, 1}, // 모든 방향 가능
{1, 0, 1, 0},
{0, 1, 0, 1},
{1, 1, 0, 0},
{0, 1, 1, 0},
{0, 0, 1, 1},
{1, 0, 0, 1},
};
static int N, M, holeY, holeX, L;
static int[][] map;
static boolean[][] visited;
static int answer;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
int T = Integer.parseInt(br.readLine());
for (int tc = 1; tc <= T; tc++) {
answer = 0;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
holeY = Integer.parseInt(st.nextToken());
holeX= Integer.parseInt(st.nextToken());
L = Integer.parseInt(st.nextToken());
map = new int[N][M];
visited = new boolean[N][M];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < M; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
} // 입력 끝
System.out.println("#" + tc + " " + bfs());
}
}
private static int bfs() {
int answer = 1;
int hours = 0;
visited[holeY][holeX] = true;
Queue<Pos> queue = new LinkedList<>();
queue.offer(new Pos(holeY, holeX));
while (!queue.isEmpty()) {
if (hours == L - 1) break; // 시간이 다 지나면 탐색 중지 (한시간은 이미 씀)
int size = queue.size();
while (size-- > 0) {
Pos out = queue.poll();
// 터널별로 갈 수 있는 방향이 전부 다르다.
int[] dirs = typeTunnel[map[out.y][out.x]];
for (int dir = 0; dir < dirs.length; dir++) {
if (dirs[dir] == 0) continue;
int ny = out.y + dy4[dir];
int nx = out.x + dx4[dir];
if (ny < 0 || nx < 0 || ny >= N || nx >= M) continue; // 범위 체크
if (map[ny][nx] == 0) continue; // 다음칸에 터널이 아예 없는 경우
if (visited[ny][nx]) continue; // 이미 방문한 경우
if (typeTunnel[map[ny][nx]][(dir + 2) % 4] == 1) { // 다음 칸에서 터널이 이어지는 경우에만 진행
visited[ny][nx] = true;
queue.offer(new Pos (ny, nx));
++answer;
}
}
}
++hours;
}
return answer;
}
static class Pos {
int y, x;
public Pos(int y, int x) {
this.y = y;
this.x = x;
}
}
}
DFS
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Solution_1953_탈주범검거DFS {
// 상 우 하 좌
static final int[] dy4 = {-1, 0, 1, 0};
static final int[] dx4 = {0, 1, 0, -1};
static final int[][] typeTunnel = { // 터널 종류별로 4방향에 대해 뚫려 있는지 여부
{0, 0, 0, 0},
{1, 1, 1, 1}, // 모든 방향 가능
{1, 0, 1, 0},
{0, 1, 0, 1},
{1, 1, 0, 0},
{0, 1, 1, 0},
{0, 0, 1, 1},
{1, 0, 0, 1},
};
static int N, M, holeY, holeX, L;
static int[][] map;
static boolean[][] visited;
static boolean[][] mark;
static int answer;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
int T = Integer.parseInt(br.readLine());
for (int tc = 1; tc <= T; tc++) {
answer = 0;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
holeY = Integer.parseInt(st.nextToken());
holeX= Integer.parseInt(st.nextToken());
L = Integer.parseInt(st.nextToken());
map = new int[N][M];
visited = new boolean[N][M];
mark = new boolean[N][M];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < M; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
} // 입력 끝
dfs(holeY, holeX, 1);
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (mark[i][j]) ++answer;
}
}
System.out.println("#" + tc + " " + answer);
}
}
private static void dfs(int sy, int sx, int hours) {
mark[sy][sx] = true;
if (hours == L) {
return;
}
// 터널별로 갈 수 있는 방향이 전부 다르다.
int[] dirs = typeTunnel[map[sy][sx]];
for (int dir = 0; dir < dirs.length; dir++) {
if (dirs[dir] == 0) continue;
int ny = sy + dy4[dir];
int nx = sx + dx4[dir];
if (ny < 0 || nx < 0 || ny >= N || nx >= M) continue;
if (map[ny][nx] == 0) continue; // 다음칸에 터널이 아예 없는 경우
if (visited[ny][nx]) continue; // 이미 방문한 경우
if (typeTunnel[map[ny][nx]][(dir + 2) % 4] == 1) { // 다음 칸에서 터널이 이어지는 경우에만 진행
visited[ny][nx] = true;
dfs(ny, nx, hours + 1);
visited[ny][nx] = false; // 백트래킹
}
}
}
static class Pos {
int y, x;
public Pos(int y, int x) {
this.y = y;
this.x = x;
}
}
}
느리지만 꾸준히