(24.09.30)
문제를 우선 파악해보자. mxn 크기의 배열에서 .은 빈 공간을 +은 벽을 의미한다. 입구 [1,2]꼴로 지정해준다. 한 단계별 한칸씩 이동가능(대각x)하며 가장 가까운 탈출구를 찾는 것이 목표이다. 입구는 탈출구가 아니다. 가장 짧은 경로의 이동 횟수를, 없다면 -1을 리턴하라. 탈출구는 배열 가장자리에 .으로 비어있는 공간이다.
이전에 DFS를 사용하지 않고 DFS문제를 풀다가 굉장히 힘들었던 경험이 있어 BFS를 적극 활용하였다. 또한 BFS과정에서 depth를 계산하는 코드를 GPT의 도움을 받아 queue.size()를 가져와 --하면서 flag값이 0이 됐을 경우 다시 queue.size()로 만들어 같은 레벨의 노드를 구분하게끔 하였다. 또 is_found플래그를 사용하여 검색에 실패했을 경우 -1을 반환하게 구현했더니 바로 통과할 수 있었다.
추후 최적화를 진행해보고, 우수한 코드를 기반으로 공부할 예정이다.
우선 여러 if 문을 하나로 묶어 코드를 간단히 정리하였다.
다음은 우수한 성능을 가진 코드의 예시이다.
public int nearestExit(char[][] maze, int[] entrance) {
int rowLength = maze.length;
int colLength = maze[0].length;
boolean[][] visited = new boolean[rowLength][colLength];
Queue<int[]> queue = new LinkedList<>();
queue.offer(entrance); // 큐가 다 차면 예외를 반환하는 .add와 달리 false를 반환한다.
visited[entrance[0]][entrance[1]] = true;
int steps = 0;
int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};//가능한 방향을 배열로
while (!queue.isEmpty()) {
int size = queue.size(); // Current level size
for (int i = 0; i < size; i++) {
int[] pos = queue.poll(); // .remove와 달리 비어있으면 null을 반환한다.
if ((pos[0] != entrance[0] || pos[1] != entrance[1]) &&
(pos[0] == 0 || pos[1] == 0 || pos[0] == rowLength - 1 || pos[1] == colLength - 1)) {
return steps;
} // 종료조건: 입구가 아닌 모서리인 경우 현재의 level을 리턴한다.
for (int[] direction : directions) {//모든 이동가능한 방향에 대하여
int newRow = pos[0] + direction[0];
int newCol = pos[1] + direction[1];
// IOR이 아니고 길에다 방문하지 않은 노드에 대해 enqueue를 수행한다.
if (newRow >= 0 && newCol >= 0 && newRow < rowLength && newCol < colLength &&
maze[newRow][newCol] == '.' && !visited[newRow][newCol]) {
visited[newRow][newCol] = true;
queue.offer(new int[] {newRow, newCol});
}
}
}
steps++;
}
return -1; // Return -1 if no exit is found
}
사실 큰 차이점은 없다. 다만 큐에 데이터를 넣고 뺄 때 .add와 .remove를 사용한 것과 달리 .offer과 .poll을 사용했다. 둘의 차이는 예외처리의 여부이다. 전자는 오류가 발생한 경우 예외를 반환하고 후자는 null값을 반환한다. 속도는 예외처리의 차이 때문일까? 이전에 작성한 코드에서 .offer과 .poll을 사용하여 속도를 측정해보자.
나는 큰 차이가 없었다. 그렇다면 차이는 두가지로 좁혀지는데, 아래와 같다.
- queue의 깊이를 확인하기 위해 나는 flag와 depth 변수를 사용했는데 우수한 예제에서는 for(int i=0; i<queue.size(); i++) 꼴로 사용하였다.
- 상하좌우 4가지 방향의 이동을 직접 i-1, j꼴로 입력했는데 우수한 예제에서는 int[] directions=new int[]{{-1, 0}, }꼴로 변수로 저장한 다음 for 루프를 이용해 간단히 하였다.
이동 가능한 방향은 언제든 바뀔 수 있기에 확장성을 고려해서라도 별도의 변수로 저장하는 것이 좋을 듯 하고, BFS에서 깊이를 알아내는 방법은 for을 이용한 방법이 가장 좋다는 것을 알고 가면 되겠다.
