[코테연습] 게임맵 최단거리
오늘의 문제는 깊이너비 탐색의 '게임 맵 최단거리' 문제이다.
https://school.programmers.co.kr/learn/courses/30/lessons/1844
개인적으로 BFS 의 정석을 담고 있는 문제라고 생각한다.
DFS 는 재귀함수로 구현하는 방식이었다면,
BFS 는 '최단거리' 를 구하는 문제에 자주 쓰이며, Queue 를 이용한 탐색으로 많이 구현된다고 생각한다.
이번 문제 또한 BFS > Queue > cost 순으로 생각을 정리하여 문제 풀이를 실시하였다.
먼저 int[][] 로 구현된 maps 를 boolean[][] 값으로 초기화하였다.
그이 이유는 '벽', '방문 여부' 를 확인하기 위해 새로운 변수가 필요하기 때문이다.
//maps
[[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]]
maps 를 이용하여 초기화한 boolean[][] visited 는 다음과 같다.
[[ ][O][ ][ ][ ]]
[[ ][O][ ][O][ ]]
[[ ][O][ ][ ][ ]]
[[ ][ ][ ][O][ ]]
[[O][O][O][O][ ]]
visited를 통해서 0,0 에서 n, m 으로 도달할 수 있는 방법은 2가지가 있다.
n, m 으로 도달하기 위해서 모든 경우의 수를 따져볼 필요가 있는데 이때 필요한 것이
상,하,좌,우 4개 방법으로 모두 옮겨보는 것이다.
해당 방법은 for 문과 int[] dx, int[] dy 로 가능하다
int[] dx = {1,0,-1,0};
int[] dy = {0,1,0,-1};
for (int i = 0; i < 4; i++) {
int nx = dx[i] + node.x;
int ny = dy[i] + node.y;
...
}
4개 방향 만큼 for문을 반복하고, 해당 값을 현재위치 + 다음 위치 ( dx[i] + x ), (dy[i] + y ) 로
nx, ny 값을 초기화 시킨다.
이때 nx, ny 값이 maps 의 범위를 넘지 않도록 if 문으로 제한한다.
if (nx >= 0 && ny >= 0 && nx < n && ny < m) {
}
nx 가 0보다 작지 않고, n 보다 크지 않아야하며
ny 가 0보다 작지 않고, m 보다 크지 않아야한다.
해당 조건을 만족시키는 위치 값 중에서 ([nx, ny])
방문 여부를 알기 위해 visited[nx][ny] 를 확인한다.
if (!visited[nx][ny]) {
}
방문하지 않았다면, nx, ny 에 해당하는 좌표에 방문한뒤 visited[nx][ny] 를 true 로 초기화하여
다시 방문하지 않도록한다.
===> 방문하지 않는다는 말은 양갈래로 나뉘는 길이 있을 경우에 먼저 도착하는 쪽 (Node) 에서
visited[nx][ny] = true 로 입력하기 때문에 나중에 도착하는 쪽 (Node) 에서는 양갈래로 나뉜 뒤
합치는 지점에서 더이상 반복하지 않게 된다.
즉, 더 늦는 쪽은 더이상 사용하지 않는 것이다.
반복하는 방법은 Queue 에 x,y 값을 저장하여 있을 경우 4개 방향으로 반복한다.
해당 방안을 코드로 구현하면 다음과 같다.