문제 설명
ROR 게임은 두 팀으로 나누어서 진행하며, 상대 팀 진영을 먼저 파괴하면 이기는 게임입니다. 따라서, 각 팀은 상대 팀 진영에 최대한 빨리 도착하는 것이 유리합니다.
지금부터 당신은 한 팀의 팀원이 되어 게임을 진행하려고 합니다. 다음은 5 x 5 크기의 맵에, 당신의 캐릭터가 (행: 1, 열: 1) 위치에 있고, 상대 팀 진영은 (행: 5, 열: 5) 위치에 있는 경우의 예시입니다.
!최단거리1_sxuruo.png
위 그림에서 검은색 부분은 벽으로 막혀있어 갈 수 없는 길이며, 흰색 부분은 갈 수 있는 길입니다. 캐릭터가 움직일 때는 동, 서, 남, 북 방향으로 한 칸씩 이동하며, 게임 맵을 벗어난 길은 갈 수 없습니다.
아래 예시는 캐릭터가 상대 팀 진영으로 가는 두 가지 방법을 나타내고 있습니다.
- 첫 번째 방법은 11개의 칸을 지나서 상대 팀 진영에 도착했습니다.
!최단거리2_hnjd3b.png
- 두 번째 방법은 15개의 칸을 지나서 상대팀 진영에 도착했습니다.
!최단거리3_ntxygd.png
위 예시에서는 첫 번째 방법보다 더 빠르게 상대팀 진영에 도착하는 방법은 없으므로, 이 방법이 상대 팀 진영으로 가는 가장 빠른 방법입니다.
만약, 상대 팀이 자신의 팀 진영 주위에 벽을 세워두었다면 상대 팀 진영에 도착하지 못할 수도 있습니다. 예를 들어, 다음과 같은 경우에 당신의 캐릭터는 상대 팀 진영에 도착할 수 없습니다.
!최단거리4_of9xfg.png
게임 맵의 상태 maps가 매개변수로 주어질 때, 캐릭터가 상대 팀 진영에 도착하기 위해서 지나가야 하는 칸의 개수의 최솟값을 return 하도록 solution 함수를 완성해주세요. 단, 상대 팀 진영에 도착할 수 없을 때는 -1을 return 해주세요.
문제 이해
- 두 팀으로 나뉘어서 진행되는 게임인데, 한 팀의 팀원이 되어 게임 진행
- 검은색 부분은 벽이고, 흰색으로 다녀야됨
- 동서남북 중 한 방향으로 한 칸씩만 이동 가능
- 맵은 변수로 주어질 예정이니까 최단 거리 구해라
어떻게 풀지 ?
그냥 머 간단한 탐색 알고리즘 문제인듯 (DFS/BFS)
하지만 코테 문제만 풀려는 게 아니라 개념도 다시 한 번 잡기 위한 리드미이므로 개념까지 같이 작성해보겠음
근데 지금은 내 개인 공부를 위해 dfs와 bfs로 모두 구현해볼 예정이지만
이런 최단거리 탐색 문제는 DFS가 아닌 BFS로 푸는 게 더 적합함
깊이우선탐색 (DFS)
어떤 노드에서부터 시작해서, 인접한 노드들을 재귀적으로 방문하여 방문한 정점은 다시 방문하지 않고, 각 분기마다 가능한 가장 멀리 있는 노드까지 탐색하는 알고리즘임
그러니까 그래프나 트리에서 한 방향으로, 끝까지 들어간 다음 더이상 갈 곳이 없으면 이전 갈림길로 돌아와 다른 길을 탐색하는 방식
쉽게 말해서, 한 방향으로 최대한 쑤셔보고, 막히면 다른 방향으로 틀어보고 이런식으로
이런 그래프가 있다고 하면
1
/ \
2 3
/ \ \
4 5 61번에서부터 DFS를 시작한다고 해보자. (왼쪽부터 탐색)
일단 1 → 2 → 4 ⇒ 4에서 막혔으니 2로 돌아가서 다른 방향 탐색 2 → 5 ⇒ 5에서 막혔으니 1로 돌아가서 다른 방향 탐색 1 → 3 → 6 ⇒ 6에서 막혔으니 3이나 1로 돌아가서 다른 방향을 탐색, 하지만 달리 뻗어갈 곳이 없음 (끝)
따라서 방문 순서는
1 -> 2 -> 4 -> 5 -> 3 -> 6이 됨
DFS에서 가장 중요한 점 ?
개인적으로 DFS 문제를 보면 다음 세 가지만 고려해보면 쉽다고 생각함
1. 현재 위치가 어디인가 ?
2. 방문한 곳인지 어떻게 확인할 것인가 ?
3. 현재 위치에서 어디로 이동할 수 있는가 ?예를 들어 그래프 문제라면, dfs(현재노드) 라는 코드 안에서
1. 현재 노드 방문 처리
2. 현재 노드와 연결된 노드들 확인
3. 아직 방문하지 않은 노드가 있다면 dfs(다음노드)를 반복하면 됨
2차원 배열에서의 DFS
사실 이 문제도 그렇고, 내 경험상 코테 문제에서는 그래프 형태보다 이 형태가 더 많음
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이건 이번 문제의 예제 중 하나임
DFS를 이용하면 현재 위치와 연결된 영역을 찾을 수 있음
현재 위치가 (x, y) 라고 하면, 네 방향(동서남북)을 확인하면 됨
위 x-1, y
아래 x+1, y
왼쪽 x, y-1
오른쪽 x, y+1나도 어디서 주워서 배운 코드이긴 하지만, 자바로 봤을 때 보통 이렇게 작성하는 거 같음
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};아무튼 위 2차원 그래프 예제를 한 번 따라가보겠다.
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-
(0, 0)에서 시작 -
아래
(0, 1)에 1이 있음 -
아래
(0, 2)에 1이 있음 -
아래
(0, 3)에 1이 있음 -
오른쪽
(1, 3)에 1이 있음 -
오른쪽
(2, 3)에 1이 있음 -
위
(2, 2)와 오른쪽(3, 2)에 1이 있음- 위
(2, 1)에 1이 있음 - 위
(2, 0)에 1이 있음 - 오른쪽
(3, 0)에 1이 있음 - 오른쪽
(4, 0)에 1이 있음 - 아래
(4, 1)에 1이 있음 - 아래
(4, 2)에 1이 있음 - 아래
(4, 3)에 1이 있음 - 아래
(4, 4)에 1이 있음
- 오른쪽
(4, 2)에 1이 있음 - 아래
(4, 3)에 1이 있음 - 아래
(4, 4)에 1이 있음
- 위
이렇게 해서 결국 연결된 모든 1 을 방문함
DFS 코드
static int[][] map = {
{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}
};
static boolean[][] visited = new boolean[5][5];
static int[] dx = {0, 0, -1, 1};
static int[] dy = {-1, 1, 0, 0};
static int minDistance = Integer.MAX_VALUE;
static void dfs(int x, int y, int distance) {
// 이미 구해놓은 최단거리보다 길면 볼 필요도 없기 때문에 return
if (distance >= minDistance) {
return;
}
// (4, 4)에 도달하면 끝
if (x == 4 && y == 4) {
minDistance = distance;
return;
}
// 방문 처리 (나 이 노드 들렸다 표시해놓는 거임)
visited[y][x] = true;
// 동, 서, 남, 북 확인
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
// 범위 밖인 경우 스킵
if (nx < 0 || nx >= 5 || ny < 0 || ny >= 5) {
continue;
}
// 벽 스킵
if (map[ny][nx] == 0) {
continue;
}
// 이미 방문한 노드 스킵
if (visited[ny][nx]) {
continue;
}
// 재귀
dfs(nx, ny, distance + 1);
}
// 혹시나 다른 경로에서 다시 들릴 수 있기 때문에 재사용할 수 있도록
visited[y][x] = false;
}
public static void main(String[] args) {
// 시작하는 위치도 세어야 하기 때문에 1로 시작
dfs(0, 0, 1);
if (minDistance == Integer.MAX_VALUE) {
System.out.println(-1);
} else {
System.out.println(minDistance);
}
}DFS라는 개념을 처음 접하거나 익숙치 않으면 어렵게 느껴질 수 있지만
코드 자체만 두고 보면 엄청 단순하고 쉬운 코드임
지금은 DFS로 최단 거리 탐색을 하기 때문에 이런 저런 코드가 추가됐는데
DFS는 최단거리 대신 모든 경우의 수나 조합, 순열 같은 문제 나오면 쓰기 좋고
BFS는 최단거리, 최소시간 이런 거 풀기 좋음
→ 프로그래머스 템플릿에 맞게 수정해서 제출했는데 테스트 케이스는 모두 통과했으나, 효율성 테스트에서는 모두 시간 초과로 실패함. 역시 이런 문제는 BFS가 맞다
너비 우선 탐색 (BFS)
얘는 DFS랑 다르게 한 곳부터 찔러보는 게 아니라
인접한 노드를 먼저 탐색해나가는 방법임
DFS는 깊게, BFS는 넓게
아까 DFS에서 예시로 든 그래프임
1
/ \
2 3
/ \ \
4 5 6DFS는 1 → 2 → 4 → 5 → 3 → 6 순서였는데
BFS는 1 → 2 → 3 → 4 → 5 → 6
BFS의 기본 동작
1. 시작점을 큐에 넣는다.
2. 방문 처리한다.
3. 큐에서 하나 꺼낸다.
4. 현재 위치에서 갈 수 있는 곳을 찾는다.
5. 아직 방문하지 않은 곳을 큐에 넣는다.
6. 방문 처리한다.
7. 큐가 빌 때까지 반복BFS 예제 코드
BFS 문제를 여러 개 풀어봤지만 코드 모양은 거의 비슷함
조금 과장해서 아래 코드 외워놓으면 모든 BFS 문제를 풀 수 있을 정도임
// 1차원 배열
Queue<Integer> q = new ArrayDeque<>();
q.offer(start);
visited[start] = true;
while (!q.isEmpty()) {
int current = q.poll();
for (int next : graph[current]) {
if (visited[next]) {
continue;
}
visited[next] = true;
q.offer(next);
}
}
// 2차원 배열
Queue<int[]> q = new ArrayDeque<>();
q.offer(new int[]{startX, startY});
visited[startY][startX] = true;
while (!q.isEmpty()) {
int[] current = q.poll();
int x = current[0];
int y = current[1];
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (범위 밖) {
continue;
}
if (갈 수 없는 곳) {
continue;
}
if (visited[ny][nx]) {
continue;
}
visited[ny][nx] = true;
q.offer(new int[]{nx, ny});
}
}DFS에서는 dfs(nx, ny)를 통해 다음 위치로 바로 들어가버리는데
BFS는 “여기는 나중에 방문해야겠다.” 하고 큐에 저장해놓는 방식임
그럼 위 코드의 큐에서 무슨 일이 발생하느냐 ?
아래와 같은 간단한 그래프가 있다고 해보자.
A
/ \
B C
/ \ / \
D E F GBFS를 A부터 시작하면
A → B → C → D → E → F → G 순서로 탐색함
이때 큐를 살펴보면
1. Queue = [A]
2. A 방문 -> Queue = []
3. B, C 발견 -> Queue = [B, C]
4. B 방문 -> Queue = [C]
5. D, E 발견 -> Queue = [C, D, E]
6. C 방문 -> Queue = [D, E]
7. F, G 발견 -> Queue = [D, E, F, G]
8. 더이상 갈 노드가 없으니 큐에 남아있는 D → E → F → G 순으로 탐색그래서 이 코드가 왜 최단거리를 보장할까 ???
사실상 이 개념을 이해하면 BFS를 이해했다고 볼 수 있음 (내 생각 ㅎ)
시작점에서부터
1번 이동해서 갈 수 있는 곳
2번 이동해서 갈 수 있는 곳
3번 이동해서 갈 수 있는 곳
…
을 탐색했을 때, “목적지에 처음 도착했다면 이보다 더 적은 이동을 도착하는 경로는 없다” 가 보장됨
쉽게 말하면, 예를 들어 4번 이동해서 목적지에 도착했다고 가정해보자 ?
이 말은 즉슨 1번, 2번, 3번 이동했을 땐 목적지에 도착하지 못했다는 거임
그렇기 때문에 나중에 5번, 6번 이동해서 목적지에 도착할 수 있다고 해도
4번 이동해서 목적지에 도달하는 게 최소 거리라는 게 보장이 됨
코드
import java.util.ArrayDeque;
import java.util.Queue;
public class Main2 {
static int[] dx = {0, 0, -1, 1};
static int[] dy = {-1, 1, 0, 0};
public static int solution(int[][] maps) {
int n = maps.length;
int m = maps[0].length;
boolean[][] visited = new boolean[n][m];
Queue<int[]> q = new ArrayDeque<>();
q.offer(new int[]{0, 0, 1});
visited[0][0] = true;
while (!q.isEmpty()) {
int[] current = q.poll();
int x = current[0];
int y = current[1];
int distance = current[2];
if (x == m - 1 && y == n - 1) {
return distance;
}
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 0 || nx >= m || ny < 0 || ny >= n) {
continue;
}
if (maps[ny][nx] == 0) {
continue;
}
if (visited[ny][nx]) {
continue;
}
visited[ny][nx] = true;
q.offer(new int[]{nx, ny, distance + 1});
}
}
return -1;
}
public static void main(String[] args) {
int[][] map = {
{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}
};
System.out.println(solution(map));
}
}작동 방식이 어떻게 되느냐 ?
q.offer(new int[]{0, 0, 1});를 통해 x = 0, y = 0, distance = 1 을 넣고
int[] current = q.poll();로 큐에서 가장 오래 기다린 위치를 꺼냄.
q.offer(new int[]{nx, ny, distance + 1});그리고 위 코드로 그 위치에서 갈 수 있는 다음 칸을 찾으면 큐에는 자연스럽게
거리 1짜리
거리 2짜리
거리 2짜리
거리 3짜리
거리 3짜리
거리 3짜리
...순서로 들어가게 됨
진짜 오랜만에 코테 문제를 풀어보는 거라 개념 공부를 좀 열심히 해봤음
DFS, BFS도 오랜만에 풀어보는 거라서 국룰 코드 까먹고 있었는데 다시 한 번 상기할 수 있는 좋은 기회가 된 듯