[Java] 프로그래머스(level-2) - 게임 맵 최단거리
문제 풀이
이 문제는 그래프 탐색 알고리즘 를 이용해 풀 수 있는 문제이다. DFS나 BFS 모두를 이용할 수 있지만 필자는 너비우선탐색인 BFS를 이용했다.
아이디어 도출
이 문제는 BFS를 이용해 캐릭터의 위치인 (0,0) 부터 게임 맵을 탐색해가며 상대방 진영의 위치인 `(N,M) 위치까지의 최단 이동거리를 구하면 된다.
상대방 진영까지의 최단거리를 구하기 위해 생각한 아이디어는 다음과 같다.
(0,0)위치부터 벽이 아닌 이동할 수 있는 칸을 탐색해가며 이동한다.- 캐릭터를 이동해가며 위치마다 이동한 거리를 기록한다.
- 상대방 진영에 도착했다면, 상대방 진영의 위치인
(N,M)에 기록된 이동거리를 반환한다.이때, 만약
(N,M)위치에 이동거리가 1이라면 주변이 벽(0)으로 막혀 상대방 진영에 도착할 수 없는 것이기에 -1을 반환한다.
위와 같이 BFS의 원리만 잘 이해하고 있다면 쉽게 풀 수 있다.
다음으로 문제 풀이를 위해 작성한 코드는 아래와 같다.
작성 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
import java.util.*;
class Solution {
// 상,하,좌,우로 탐색할 dx, dy 배열
static int[] dx = new int[]{1, 0, -1, 0};
static int[] dy = new int[]{0, 1, 0, -1};
// 방문 여부를 체크할 배열
static boolean[][] visited;
// 전역으로 사용할 게임 맵 2차원 배열
static int[][] map;
// 게임 맵의 크기 NXM
static int N, M;
public int solution(int[][] maps) {
// 게임 맵의 크기 N과 M 초기화
N = maps.length;
M = maps[0].length;
// 게임 맵 배열 초기화
map = maps;
// 방문 배열 초기화
visited = new boolean[N][M];
// 캐릭터의 위치인 0,0 위치에서 BFS 함수 호출
BFS(0, 0);
/**
* BFS 탐색이 종료되면, map 배열의 N,M 위치에 기록된 이동거리 반환
* 만약, 벽에 가로막혀 상대방 진영에 도착하지 못한다면, -1 반환
*/
if(map[N-1][M-1] > 1) {
return map[N-1][M-1];
} else {
return -1;
}
}
static void BFS(int x, int y) {
Queue<int[]> q = new LinkedList<>();
q.offer(new int[]{x, y});
visited[x][y] = true;
while(!q.isEmpty()) {
int[] now = q.poll();
for(int dir=0; dir<4; dir++) {
int i = now[0] + dx[dir];
int j = now[1] + dy[dir];
/**
* 게임 맵 배열의 범위를 벗어나지 않고 이동할 수 있는 칸인지를 확인해간다.
* 이동할 수 있는 칸으로 이동할 경우, map 배열 각 위치에 이동거리를 갱신한다.
*/
if(isRange(i, j)) {
if(!visited[i][j] && map[i][j] != 0) {
visited[i][j] = true;
map[i][j] = map[now[0]][now[1]] + 1;
q.offer(new int[]{i, j});
}
}
}
}
}
static boolean isRange(int x, int y) {
if(0<=x && 0<=y && x<N && y<M) {
return true;
}
return false;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[][] maps = new int[][]{{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}};
// int[][] maps = new int[][]{{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}};
sol.solution(maps);
}
}
회고
출처
- —
- 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.