문제 정보
2178번: 미로 탐색
첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.
www.acmicpc.net
핵심
BFS 알고리즘을 활용하여 문제를 풀이한다
큐를 사용할 때, Node 클래스를 만들어서 현재 위치와 Depth를 기록하고 이를 활용하였다
또한 현재 위치가 Invalid한지 확인하는 것, 갈 수 있는 위치인지(해당 Map의 값이 1인지) 확인하는 것 또한 빠뜨릴 수 있다
내가 가장 생각을 많이 했던 부분은 다음과 같다
while (!queue.isEmpty()) {
Node popItem = queue.poll();
int row = popItem.row;
int col = popItem.col;
int depth = popItem.depth;
visited[row][col] = true;
// Check valid position
// Queue addBFS에서 이 방식처럼 큐에서 노드를 pop한 후에 visited 표시를 하면, 큐는 First in First Out이기 때문에(처음 들어간 노드가 가장 빨리 나옴) 해당 노드가 방문되지 않았다고 알고
for (int i = 0; i < 4; i++) {
if (i == 0 || i == 1) {
if (isValidPosition(row + arroundCurrent[i], col)) {
queue.add(new Node(row + arroundCurrent[i], col, depth + 1));
}
} else {
if (isValidPosition(row, col + arroundCurrent[i - 2])) {
queue.add(new Node(row, col + arroundCurrent[i - 2], depth + 1));
}
}
}큐에 계속 해당 노드를 경로에 집어넣는, 중복된 삽입이 계속 이루어지고
4 6
110110
110110
111111
111101
Row : 0 Col : 0 Depth : 1
Row : 1 Col : 0 Depth : 2
Row : 0 Col : 1 Depth : 2
Row : 2 Col : 0 Depth : 3
Row : 1 Col : 1 Depth : 3
Row : 1 Col : 1 Depth : 3
Row : 3 Col : 0 Depth : 4
Row : 2 Col : 1 Depth : 4
Row : 2 Col : 1 Depth : 4
Row : 2 Col : 1 Depth : 4
Row : 3 Col : 1 Depth : 5
Row : 3 Col : 1 Depth : 5
Row : 2 Col : 2 Depth : 5
Row : 3 Col : 1 Depth : 5
Row : 2 Col : 2 Depth : 5
Row : 3 Col : 1 Depth : 5
Row : 2 Col : 2 Depth : 5
Row : 3 Col : 2 Depth : 6
Row : 3 Col : 2 Depth : 6
Row : 3 Col : 2 Depth : 6
Row : 2 Col : 3 Depth : 6
Row : 3 Col : 2 Depth : 6
Row : 3 Col : 2 Depth : 6
Row : 2 Col : 3 Depth : 6
Row : 3 Col : 2 Depth : 6
Row : 3 Col : 2 Depth : 6
Row : 2 Col : 3 Depth : 6
Row : 3 Col : 3 Depth : 7
Row : 3 Col : 3 Depth : 7
Row : 3 Col : 3 Depth : 7
Row : 1 Col : 3 Depth : 7
Row : 3 Col : 3 Depth : 7
Row : 2 Col : 4 Depth : 7
Row : 3 Col : 3 Depth : 7
Row : 3 Col : 3 Depth : 7
Row : 1 Col : 3 Depth : 7
Row : 3 Col : 3 Depth : 7
Row : 2 Col : 4 Depth : 7
Row : 3 Col : 3 Depth : 7
Row : 3 Col : 3 Depth : 7
Row : 1 Col : 3 Depth : 7
Row : 3 Col : 3 Depth : 7
Row : 2 Col : 4 Depth : 7
Row : 0 Col : 3 Depth : 8
Row : 1 Col : 4 Depth : 8
Row : 1 Col : 4 Depth : 8
Row : 2 Col : 5 Depth : 8
Row : 0 Col : 3 Depth : 8
Row : 1 Col : 4 Depth : 8
Row : 1 Col : 4 Depth : 8
Row : 2 Col : 5 Depth : 8
Row : 0 Col : 3 Depth : 8
Row : 1 Col : 4 Depth : 8
Row : 1 Col : 4 Depth : 8
Row : 2 Col : 5 Depth : 8
Row : 0 Col : 4 Depth : 9
Row : 0 Col : 4 Depth : 9
Row : 0 Col : 4 Depth : 9
Row : 3 Col : 5 Depth : 9
9이렇게 많은 경우의 수가 만들어지게 된다
따라서, 해결 방법은 큐에 노드를 집어넣음과 동시에 방문했음을 알리고
해당 노드가 큐에 다시는 들어가지 않도록 표시해주어야 한다
while (!queue.isEmpty()) {
Node popItem = queue.poll();
int row = popItem.row;
int col = popItem.col;
int depth = popItem.depth;for (int i = 0; i < 4; i++) {
if (i == 0 || i == 1) {
if (isValidPosition(row + arroundCurrent[i], col)) {
queue.add(new Node(row + arroundCurrent[i], col, depth + 1));
visited[row + arroundCurrent[i]][col] = true;
}
} else {
if (isValidPosition(row, col + arroundCurrent[i - 2])) {
queue.add(new Node(row, col + arroundCurrent[i - 2], depth + 1));
visited[row][col + arroundCurrent[i - 2]] = true;
}
}
}이런식으로 하면 메모리 초과가 발생하지 않고, 효율적인 풀이가 가능해진다
4 6
110110
110110
111111
111101
Row : 0 Col : 0 Depth : 1
Row : 1 Col : 0 Depth : 2
Row : 0 Col : 1 Depth : 2
Row : 2 Col : 0 Depth : 3
Row : 1 Col : 1 Depth : 3
Row : 3 Col : 0 Depth : 4
Row : 2 Col : 1 Depth : 4
Row : 3 Col : 1 Depth : 5
Row : 2 Col : 2 Depth : 5
Row : 3 Col : 2 Depth : 6
Row : 2 Col : 3 Depth : 6
Row : 3 Col : 3 Depth : 7
Row : 1 Col : 3 Depth : 7
Row : 2 Col : 4 Depth : 7
Row : 0 Col : 3 Depth : 8
Row : 1 Col : 4 Depth : 8
Row : 2 Col : 5 Depth : 8
Row : 0 Col : 4 Depth : 9
Row : 3 Col : 5 Depth : 9
9아까처럼, 중복된 노드를 지나가지 않고 짧은 시간에 답이 구해지는 것을 볼 수 있었다
풀이
import java.io.*;
import java.util.*;
class Main {
static int[][] miro;
static boolean[][] visited;
static int N;
static int M;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input = br.readLine().split(" ");
N = Integer.parseInt(input[0]);
M = Integer.parseInt(input[1]);
miro = new int[N][M];
visited = new boolean[N][M];
for (int i = 0; i < N; i++) {
String[] inputRow = br.readLine().split("");
for (int j = 0; j < M; j++) {
miro[i][j] = Integer.parseInt(inputRow[j]);
}
}
int result = BFS(0, 0);
System.out.println(result);
}
static int[] arroundCurrent = {-1, 1};
public static int BFS(int currentRow, int currentCol) {
Queue<Node> queue = new LinkedList<>();
queue.add(new Node(currentRow, currentCol, 1));
visited[currentRow][currentCol] = true;
while (!queue.isEmpty()) {
Node popItem = queue.poll();
int row = popItem.row;
int col = popItem.col;
int depth = popItem.depth;
// DEBUG
System.out.println("Row : " + row + " Col : " + col + " Depth : " + depth);
// End condition
if (row == N - 1 && col == M - 1)
return depth;
// Check Around Current Node
for (int i = 0; i < 4; i++) {
if (i == 0 || i == 1) {
if (isValidPosition(row + arroundCurrent[i], col)) {
queue.add(new Node(row + arroundCurrent[i], col, depth + 1));
visited[row + arroundCurrent[i]][col] = true;
}
} else {
if (isValidPosition(row, col + arroundCurrent[i - 2])) {
queue.add(new Node(row, col + arroundCurrent[i - 2], depth + 1));
visited[row][col + arroundCurrent[i - 2]] = true;
}
}
}
}
return -1;
}
public static boolean isValidPosition(int row, int col) {
return (row >= 0 && row < N) && (col >= 0 && col < M) && (!visited[row][col])
&& (miro[row][col] == 1);
}
}
class Node {
int row;
int col;
int depth;
public Node(int row, int col, int depth) {
this.row = row;
this.col = col;
this.depth = depth;
}
}Source Code on GitHub
댓글