[프로그래머스/1844] 게임 맵 최단거리
in Study / Coding Test
☑️ 문제
☑️ 필요한 지식
(x, y)의 상하좌우로의 좌표 변화량
dx,dy는x,y좌표의 변화량이므로 상하좌우 네 방향에 대해서 다음 값을 가진다.상 하 좌 우 dx 0 0 -1 1 dy -1 1 0 0 - 여러 개의 방향을 다루려면 해당 표의 값을 배열에 담아야 한다.
인덱스 0은 상, 인덱스 1은 하, 인덱스 2는 좌, 인덱스 3은 우
private static final int[] dx = {0, 0, -1, -1}; private static final int[] dy = {-1, 1, 0, 0};
예시 :
(x, y)를 오른쪽으로 한 칸 이동시키는 코드x += dx[0]; y += dy[0];
☑️ 풀이
DFS로 작성한 코드
class Solution {
int[] X= {0, 0, 1, -1};
int[] Y= {1, -1, 0, 0};
int[][] gMaps;
boolean[][] visited;
int min = 10000;
int endX;
int endY;
public int solution(int[][] maps) {
int answer = 0;
gMaps = maps;
visited = new boolean [maps.length][maps[0].length];
endX = maps.length -1;
endY = maps[0].length -1;
// 시작점에서 count 1로 시작 (자기 자신 포함)
dfs(0, 0, 1);
answer = (min == 10000 ? -1 : min);
return answer;
}
void dfs(int x, int y, int count) {
// 범위를 벗어나거나 이미 방문한 경우, 또는 이동할 수 없는 칸인 경우 리턴
if(x < 0 || y < 0 || x > endX || y > endY || visited[x][y] == true || gMaps[x][y] == 0 ) {
return;
}
// 도착 지점에 도달한 경우
if (x == endX && y == endY) {
min = Math.min(min, count);
return;
}
// 현재 위치 방문 처리
visited[x][y] = true;
// 상하좌우로 DFS 탐색
for (int i = 0; i < X.length; i++) {
dfs(x+X[i], y+Y[i], count + 1);
}
// 탐색 후에는 방문 기록을 해제 (백트래킹)
visited[x][y] = false;
}
}
DFS 풀이 실행결과
- 테스트 케이스는 모두 통과하지만, 효율성 테스트는 단 한 개도 통과하지 못했다.
- DFS를 이용하게 되면, 게임 맵에서 끝까지 깊게 내려가서 탐색한 후, 처음으로 이동해서 다시 탐색하는 과정을 거쳐야 해서 효율성이 매우 낮다. (모든 경로를 탐색함)
- BFS의 경우, Queue를 이용해서 게임 맵을 얕게 탐색하기 때문에 최단 거리를 계산하기 매우 좋다. (도착점에 도달하는 순간 종료됨)
BFS로 작성한 코드
//시간: 0.56ms
//메모리: 83.5MB
import java.util.*;
class Point {
public int x;
public int y ;
Point (int x, int y) {
this.x = x;
this.y = y;
}
}
class Solution {
static int n;
static int m;
static int[][] maps;
static boolean[][] visited;
// 좌 우 상 하
int[] X = {-1, 1, 0, 0};
int[] Y = {0, 0, 1, -1};
public int solution(int[][] maps) {
// 상대방 진영 위치 (n, m)
n = maps.length - 1;
m = maps[0].length - 1;
this.maps = maps;
visited = new boolean[n + 1][m + 1];
bfs(0, 0);
return visited[n][m] ? maps[n][m] : -1;
}
public void bfs(int x, int y) {
Queue<Point> queue = new LinkedList<>();
queue.add(new Point(x, y));
visited[x][y] = true;
while (!queue.isEmpty()) {
Point point = queue.poll();
for (int i = 0; i < X.length; i++) {
int nx = point.x + X[i];
int ny = point.y + Y[i];
if (nx <= n && ny <= m && nx >= 0 && ny >= 0 && !visited[nx][ny] && maps[nx][ny] == 1) {
maps[nx][ny] = maps[point.x][point.y] + 1;
queue.add(new Point(nx, ny));
visited[nx][ny] = true;
}
}
}
}
}
bfs탐색을 완료한 후,maps[n][m]을 방문한 경우와 하지 않은 경우로 나누어서 정답을 리턴한다.- 방문한 경우,
maps[n][m]에 저장된 최단 거리 값을 리턴한다. - 방문하지 않은 경우,
-1를 리턴한다.
- 방문한 경우,
- 처음에
bfs의if조건에서nx <= n && ny <= m && nx >= 0 && ny >= 0을 먼저 실행하지 않아ArrayIndexOutOfBoundsException예외가 발생하였다.- 배열 범위를 먼저 검사하도록 순서를 변경하였다.
BFS 풀이 실행결과
- 효율성 테스트를 모두 통과하였다.
