문제 설명
ROR 게임은 두 팀으로 나누어서 진행하며, 상대 팀 진영을 먼저 파괴하면 이기는 게임입니다. 따라서, 각 팀은 상대 팀 진영에 최대한 빨리 도착하는 것이 유리합니다.
지금부터 당신은 한 팀의 팀원이 되어 게임을 진행하려고 합니다. 다음은 5 x 5 크기의 맵에, 당신의 캐릭터가 (행: 1, 열: 1) 위치에 있고, 상대 팀 진영은 (행: 5, 열: 5) 위치에 있는 경우의 예시입니다.
위 그림에서 검은색 부분은 벽으로 막혀있어 갈 수 없는 길이며, 흰색 부분은 갈 수 있는 길입니다. 캐릭터가 움직일 때는 동, 서, 남, 북 방향으로 한 칸씩 이동하며, 게임 맵을 벗어난 길은 갈 수 없습니다.아래 예시는 캐릭터가 상대 팀 진영으로 가는 두 가지 방법을 나타내고 있습니다.
- 첫 번째 방법은 11개의 칸을 지나서 상대 팀 진영에 도착했습니다.
- 두 번째 방법은 15개의 칸을 지나서 상대팀 진영에 도착했습니다.
위 예시에서는 첫 번째 방법보다 더 빠르게 상대팀 진영에 도착하는 방법은 없으므로, 이 방법이 상대 팀 진영으로 가는 가장 빠른 방법입니다.
만약, 상대 팀이 자신의 팀 진영 주위에 벽을 세워두었다면 상대 팀 진영에 도착하지 못할 수도 있습니다. 예를 들어, 다음과 같은 경우에 당신의 캐릭터는 상대 팀 진영에 도착할 수 없습니다.
게임 맵의 상태 maps가 매개변수로 주어질 때, 캐릭터가 상대 팀 진영에 도착하기 위해서 지나가야 하는 칸의 개수의 최솟값을 return 하도록 solution 함수를 완성해주세요. 단, 상대 팀 진영에 도착할 수 없을 때는 -1을 return 해주세요.
제한사항
- maps는 n x m 크기의 게임 맵의 상태가 들어있는 2차원 배열로, n과 m은 각각 1 이상 100 이하의 자연수입니다.
- n과 m은 서로 같을 수도, 다를 수도 있지만, n과 m이 모두 1인 경우는 입력으로 주어지지 않습니다.
- maps는 0과 1로만 이루어져 있으며, 0은 벽이 있는 자리, 1은 벽이 없는 자리를 나타냅니다.
- 처음에 캐릭터는 게임 맵의 좌측 상단인 (1, 1) 위치에 있으며, 상대방 진영은 게임 맵의 우측 하단인 (n, m) 위치에 있습니다.
입출력 예
| maps | answer |
|---|---|
| [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]] | 11 |
| [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]] | -1 |
나의 풀이
BFS 문제 중 BFS의 느낌을 익히기에 아주 좋은 문제였다고 생각한다. 우선 이 문제를 DFS로도 풀 수도 있다고는 하는 것 같은데 아직 BFS, DFS를 능숙하게 다루지 못하기 때문에 평균적으로 최단 거리를 구하는 데에 더욱 유리한 BFS를 사용하여 풀어보았다.
우선, 여기서 왜 BFS가 유리한지를 보도록 하자
출처 : https://han-joon-hyeok.github.io/posts/programmers-game-map-shortest-path/
DFS 문제점?
하지만, DFS 는 2가지 단점 때문에 이 문제에서 요구하는 정답을 만족할 수 없다.
첫째, DFS 는 모든 가능한 경우의 수를 탐색하기 때문에 미로의 크기가 커질 경우 연산 횟수가 기하급수적으로 늘어나기 때문에 실행 시간도 같이 증가한다.
예를 들어, 다음과 같은 미로가 있다고 해보자.
1 🏃♂️ 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 👑 첫 번째 갈림길인
(3, 3)지점에서 선택할 수 있는 경로의 수는 3가지다. 그리고 두 번째 갈림길인(7, 3)에서도 선택할 수 있는 경로의 수는 3가지다. 따라서 도착 지점인(9, 6)까지 도달하는 모든 경우의 수는 32=932=9 이다. 만약, 갈림길이 2개가 아니라 1000 개면 경로의 수는 3100031000 이 될 것이다.둘째, DFS 는 최단 거리를 보장하지 못한다. 사실 위와 같은 코드에서는 해를 발견하면 바로 종료하는 것이 아니라, 모든 경우의 수를 탐색하기 때문에 완전 탐색에 가깝다. 하지만 해를 발견하면 종료하는 DFS 에서는 발견한 해가 최적해라는 것을 보장하지는 않는다.
예를 들어, 다음과 같은 미로가 있다고 해보자. 이때, 해를 찾으면 다른 유망한 경로는 찾지 않고 바로 종료한다고 가정한다.
1 🏃♂️ 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 👑 탐색하는 순서가
상 - 우 - 하 - 좌순이라면, 다음과 같이 탐색할 것이다.
1 🏃♂️ 1 1 1 2 🏃♂️ 1 1 3 🏃♂️ 7 🏃♂️ 8 🏃♂️ 9 🏃♂️ 4 🏃♂️ 5 🏃♂️ 6 🏃♂️ 10 🏃♂️ 1 1 11 🏃♂️ 만약, 탐색하는 순서가
하 - 우 - 상 - 좌순이라면, 다음과 같이 탐색할 것이다.
1 🏃♂️ 1 1 1 2 🏃♂️ 1 1 3 🏃♂️ 1 1 1 4 🏃♂️ 5 🏃♂️ 6 🏃♂️ 1 7 🏃♂️ 8 🏃♂️ 9 🏃♂️ 이를 통해 탐색하는 순서에 따라 해가 바뀔 수 있으며, 발견한 해가 반드시 최적해가 아니라는 것을 알 수 있다.
따라서 최단 거리를 찾기 위해서는
DFS보다는**BFS**를 사용한다.
다음은 풀이 코드이다
import java.util.LinkedList;
import java.util.Queue;
class Solution {
int[] dx = {0, 0, -1, 1};
int[] dy = {1, -1, 0, 0};
class Node {
int x;
int y;
public Node(int x, int y) {
this.x = x;
this.y = y;
}
}
public int solution(int[][] maps) {
int answer = 0;
int[][] visited = new int[maps.length][maps[0].length];
bfs(maps, visited);
answer = visited[maps.length - 1][maps[0].length - 1];
if (answer == 0) {
answer = -1;
}
return answer;
}
public void bfs(int[][] maps, int[][] visited) {
Queue<Node> q = new LinkedList<>();
q.add(new Node(0, 0));
visited[0][0] = 1;
while (!q.isEmpty()) { // 더 나아갈 곳이 없을 때까지
Node node = q.poll();
int X = node.x;
int Y = node.y;
for (int i = 0; i < 4; i++) {
int newX = X + dx[i];
int newY = Y + dy[i];
// 좌표가 maps에서 벗어날 경우 패스
if (newX < 0 || newX > maps[0].length - 1 || newY < 0 || newY > maps.length - 1) {
continue;
}
// 아직 방문하지 않았고, 벽이 아닌 경우
if (visited[newY][newX] == 0 && maps[newY][newX] == 1) {
visited[newY][newX] = visited[Y][X] + 1;
q.add(new Node(newX, newY));
}
}
}
}
}BFS는 Queue를 이용한 구현이 대표적이다.
좌표의 상하좌우를 담당할 dx, dy 배열을 선언하고 Queue에 담아줄 좌표값을 위해 Node 클래스를 만들고 Node의 변수로 int x, int y를 선언한다.
이번 문제는 애초에 maps의 크기가 주어져있기 때문에 고의로 maps의 크기를 늘려 그 외부에 도착하는 순간 값을 false 혹은 0으로 바꾸어주는 작업을 진행할 수 없다. (maps의 크기 조절을 통한 아래의 2번 과정 생략이 불가)그렇기에 visited 배열 역시 maps의 크기와 같게 선언하였다.
다음으로는 bfs의 구현인데, (0, 0)부터 탐색을 시작할 것이기 때문에 새로운 Node를 생성하고 x = 0, y = 0 을 담아주고 이를 Queue에 담아준다. 좌표를 방문처리 했음을 알려주는 visited[x][y] = 1 처리 역시 해준다.
이렇게 초기 설정을 마쳤다면 BFS는 재귀가 아닌 while과 Queue를 기반으로 동작하기 때문에 while문을 작성해준다. while문의 조건은 Queue의 사이즈가 0이 아닐때까지이며, while문 내부에서 좌표의 이동처리를 진행하는데…
- 초기에 만들어두었던 상하좌우를 담당할 dx, dy를 통해 새로운 좌표값 newX, newY를 만들어준다.
- 이 좌표가 맵의 영역에 벗어나지 않았는지 판단한다.
- 맵의 영역내에 있으며 방문하지 않았고, 벽이 아닌 경우 이 새로운 좌표에 이전 좌표의 값을 더해준다.
- 이렇게 이전 좌표의 값 +1 만큼을 계속 더해나가다 보면 최종 목적지에 도착 후 몇 번 이동을 했는지 알 수 있게 된다.
- 모든 작업이 끝나면 Queue에 지금 위치를 담아주고 다시 while문을 반복한다.
이 모든 과정을 통해 정답을 구해낼 수 있었다.
