문제 링크
https://www.acmicpc.net/problem/2178
풀이
첫 번째 시도 (시간 초과)
- 처음에는 DFS로 접근해보았다. 좌표 범위 안에 있는지, 이동할 수 있는 칸인지 확인하면서 목적지에 도착했을 때 최소 이동 거리인
minMoveCnt를 업데이트했고, 그 자리에서 4방 탐색을 재귀로 수행했다.- 이동 가능 여부를 나타내는 별도의 배열을 만들지 않고, 미로 상태를 저장한 2차원 배열인
maze에서 현재 위치에 해당하는 값을1에서0으로 바꾸면서 4방 탐색을 진행했다. 4방 탐색이 끝나면 현위치의 값을 다시1로 바꾸었다.
- 이동 가능 여부를 나타내는 별도의 배열을 만들지 않고, 미로 상태를 저장한 2차원 배열인
- 하지만 결과는 TLE였다. DFS에 최적화된 문제가 아닌 것이다.
소스 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
/**
* 백준 2178번: 미로 탐색
*/
public class Main {
private static int[][] maze;
private static int[] dr = {-1, 0, 1, 0}; // y 좌표에 대한 델타값 (위에서부터 시계 방향)
private static int[] dc = {0, 1, 0, -1}; // x 좌표에 대한 델타값 (위에서부터 시계 방향)
private static int minMoveCnt, n, m;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
maze = new int[n][m];
minMoveCnt = n * m;
// 미로 초기화
for (int i = 0; i < n; i++) {
String row = br.readLine();
for (int j = 0; j < m; j++) {
maze[i][j] = row.charAt(j) - '0';
}
}
// 시작점에서 재귀 호출 시작
move(0, 0, 1);
System.out.println(minMoveCnt);
br.close();
}
public static void move(int r, int c, int cnt) {
// 좌표를 벗어나면 리턴
if (r < 0 || r >= n || c < 0 || c >= m) return;
// 이동할 수 있는 칸(1)이 아니면 리턴
if (maze[r][c] == 0) return;
// 목적지에 도착하면 minMoveCnt 갱신 후 리턴
if (r == n - 1 && c == m - 1) {
minMoveCnt = Math.min(minMoveCnt, cnt);
return;
}
// 현재 위치를 중복해서 이동하지 않도록 0으로 표시
maze[r][c] = 0;
// 네 방향으로 재귀 호출
for (int i = 0; i < 4; i++) {
move(r + dr[i], c + dc[i], cnt + 1);
}
// 0으로 표시한 현재 위치를 다시 1로 표시
maze[r][c] = 1;
}
}
두 번째 시도
- 재귀 대신 큐를 사용하여 BFS를 구현했고, 무사히 통과했다.
- 보통 이런 문제는 DFS를 잘 안쓰고 BFS를 사용한다고 한다. DFS를 사용할 경우 목적지에 도달해도 재귀가 끝나면서 다시 처음으로 돌아가는 과정이 포함되기 때문에 TLE가 뜨는 것이다.
-
예를 들어 다음과 같은 입력을 받는다고 하자.
4 6 110110 110110 111111 111101 -
이동할 때마다 현재 좌표를 콘솔에 찍어보면 다음과 같다.
-
소스 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
/**
* 백준 2178번: 미로 탐색
*/
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int[][] maze = new int[n][m];
boolean[][] visited = new boolean[n][m];
int minMoveCnt = n * m;
int[] dr = {-1, 0, 1, 0}; // y 좌표에 대한 델타값 (위에서부터 시계 방향)
int[] dc = {0, 1, 0, -1}; // x 좌표에 대한 델타값 (위에서부터 시계 방향)
// 미로 초기화
for (int i = 0; i < n; i++) {
String row = br.readLine();
for (int j = 0; j < m; j++) {
maze[i][j] = row.charAt(j) - '0';
}
}
// BFS를 사용한 방법
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[] {0, 0, 1});
while (!queue.isEmpty()) {
int[] curr = queue.poll();
int r = curr[0];
int c = curr[1];
int cnt = curr[2];
// 좌표를 벗어나면 다음 원소 추출
if (r < 0 || r >= n || c < 0 || c >= m) continue;
// 이동할 수 있는 칸(1)이 아니거나 이미 방문했으면 다음 원소 추출
if (maze[r][c] == 0 || visited[r][c]) continue;
// 현재 위치를 중복해서 이동하지 않도록 표시
visited[r][c] = true;
// 목적지에 도착하면 minMoveCnt 갱신 후 다음 원소 추출
if (r == n - 1 && c == m - 1) {
minMoveCnt = Math.min(minMoveCnt, cnt);
continue;
}
// 인접 4방향을 큐에 추가
for (int i = 0; i < 4; i++) {
queue.offer(new int[] {r + dr[i], c + dc[i], cnt + 1});
}
}
System.out.println(minMoveCnt);
br.close();
}
}