Level 2: 미로 탈출, 두 개의 BFS 연결

참고 문서

• Programmers: 미로 탈출

이 문서의 내용

• Step 1: 노드를 표현하는 클래스
• Step 2: BFS 구현
• Step 3: 두 번의 BFS 실행으로 세 개의 노드를 연결
• Step 4: 전체 코드

BFS는 노드와 노드 간 최단 거리를 계산하기 위해서 사용합니다.

문제에서는 시작 노드에서 시작해 레버 노드를 경유하고 최종적으로 도착 노드에 도달해야합니다.

BFS를 연속 실행하고 연속된 BFS 결과를 합산하는 것으로 결과를 도출합니다.

Step 1: 노드를 표현하는 클래스

길 찾기를 위한 경로는 2차원 좌표계-이중 배열로 제공됩니다. 이를 표현하고 저장하기 위한 Node 클래스를 생성합니다.

java

닫기

public class Node
{
‌public int x, y;
‌public int cost;
‌
‌public Node(int x, int y, int cost)
‌{
‌‌this.x = x;
‌‌this.y = y;
‌‌this.cost = cost;
‌}
}

코드		비고
Line 3	int x, y	2차원 좌표계 위의 x, y 좌표입니다. 각 좌표의 시작 값은 0입니다.
Line 4	int cost	BFS 실행 간 이동 거리입니다.

Step 2: BFS 구현

2차원 좌표계에서 시작 지점 bx, by에서 출발해 도착 지점 gx, gy에 도달하는 최단 거리를 계산합니다.

이때 도착 지점에 도달하면 해당 노드까지의 거리(cost)를 리턴하고, 도착하지 못하면 -1을 리턴합니다.

java

닫기

public int bfs(String[] maps, int bx, int by, int gx, int gy)
{
‌int[] dx = { 0, 1, 0, -1 };
‌int[] dy = { -1, 0, 1, 0 };
‌int h = maps.length;
‌int w = maps[0].length();
‌int x = bx, y = by;
‌boolean[][] visited = new boolean[h][w];
‌
‌Queue<Node> q = new LinkedList<>();
‌q.offer(new Node(x, y, 0));
‌visited[y][x] = true;
‌
‌while (!q.isEmpty())
‌{
‌‌Node n = q.poll();
‌‌if (n.x == gx && n.y == gy)
‌‌‌return n.cost;
‌‌for (int i = 0; i < 4; ++i)
‌‌{
‌‌‌int nx = n.x + dx[i];
‌‌‌int ny = n.y + dy[i];
‌‌‌if (nx < 0 || ny < 0 || nx >= w || ny >= h)
‌‌‌‌continue;
‌‌‌char[] s = maps[ny].toCharArray();
‌‌‌char c = s[nx];
‌‌‌if (!visited[ny][nx] && 'X' != c)
‌‌‌{
‌‌‌‌visited[ny][nx] = true;
‌‌‌‌q.offer(new Node(nx, ny, n.cost + 1));
‌‌‌}
‌‌}
‌}
‌
‌return -1;
}

코드		비고
Line 3:4	int[] dx, dy	BFS의 진행 방향을 표현하는 배열입니다.
Line 5:6	int h, w	2차원 좌표계의 높이와 길이입니다.
Line 7	int x = bx, y = by	현재 x, y 좌표입니다. 시작 값은 BFS 실행에서의 출발 좌표입니다.
Line 17:18	if (n.x == gx && n.y == gy)	목표 좌표에 도달하면 이동 거리를 리턴합니다.
Line 27:31	if (!visited[ny][nx] && 'X' != c)	문제의 규칙에 따라서 이동할 수 있는 좌표라면 BFS를 실행합니다.
Line 35	return -1	BFS가 종료되었으나 목표 좌표에 도달하지 못했다면 -1을 리턴합니다.

Step 3: 두 번의 BFS 실행으로 세 개의 노드를 연결

문제에서는 시작 노드에서 시작해 레버 노드를 경유하고 최종적으로 도착 노드에 도달해야합니다.

두 개의 노드를 잇는 경로에서 3자 노드를 반드시 경유하는 길찾기는 다음과 같이 단순화 할 수 있습니다.

시작 노드에서 3자 노드까지의 최단 거리를 계산합니다.

경유를 위한 3자 노드에서 종료 노드까지의 최단 거리를 계산합니다.

그리고나서 두 개의 최단 거리를 합산합니다.

우선 좌표계로 제공된 이중 배열 maps를 순회하면서 각 노드의 좌표를 구합니다.

그다음 두 번의 BFS를 실행하여 문제의 결과를 도출합니다.

java

닫기

public int solution(String[] maps) 
{
‌int sx = 0, sy = 0, lx = 0, ly = 0, ex = 0, ey = 0;
‌for (int y = 0; y < maps.length; ++y)
‌{
‌‌char[] s = maps[y].toCharArray();
‌‌for (int x = 0; x < s.length; ++x)
‌‌{
‌‌‌char c = s[x];
‌‌‌switch (c)
‌‌‌{
‌‌‌‌case 'S' -> {
‌‌‌‌‌sx = x;
‌‌‌‌‌sy = y;
‌‌‌‌}
‌‌‌‌case 'L' -> {
‌‌‌‌‌lx = x;
‌‌‌‌‌ly = y;
‌‌‌‌}
‌‌‌‌case 'E' -> {
‌‌‌‌‌ex = x;
‌‌‌‌‌ey = y;
‌‌‌‌}
‌‌‌}
‌‌}
‌}
‌
‌int toL = bfs(maps, sx, sy, lx, ly);
‌if (toL <= -1) return -1;
‌int toE = bfs(maps, lx, ly, ex, ey);
‌if (toE <= -1) return -1;
‌return toL + toE;
}

코드		비고
Line 3:26	int sx, sy, lx, ly, ex, ey	시작 노드(sx, sy)와 레버 노드(lx, ly) 그리고 도착 노드(ex, ey)를 구합니다.
Line 28:29	toL = bfs()	시작 노드(sx, sy)부터 레버 노드(lx, ly)까지 최단 거리를 BFS로 계산합니다. 만약 경로를 찾지 못하면 -1을 리턴합니다.
Line 30:31	toE = bfs()	레버 노드(lx, ly)부터 도착 노드(ex, ey)까지 최단 거리를 BFS로 계산합니다. 만약 경로를 찾지 못하면 -1을 리턴합니다.
Line 32	return toL + toE	두 번의 BFS 결과를 합산하여 리턴합니다.

Step 4: 전체 코드

각 단계별로 구성된 전체 코드는 다음을 참고합니다.

java

닫기

import java.util.*;

public class Solution
{
‌public class Node
‌{
‌‌public int x, y;
‌‌public int cost;
‌‌
‌‌public Node(int x, int y, int cost)
‌‌{
‌‌‌this.x = x;
‌‌‌this.y = y;
‌‌‌this.cost = cost;
‌‌}
‌}
‌
‌public int solution(String[] maps) {
‌‌int sx = 0, sy = 0, lx = 0, ly = 0, ex = 0, ey = 0;
‌‌for (int y = 0; y < maps.length; ++y)
‌‌{
‌‌‌char[] s = maps[y].toCharArray();
‌‌‌for (int x = 0; x < s.length; ++x)
‌‌‌{
‌‌‌‌char c = s[x];
‌‌‌‌switch (c)
‌‌‌‌{
‌‌‌‌‌case 'S' -> {
‌‌‌‌‌‌sx = x;
‌‌‌‌‌‌sy = y;
‌‌‌‌‌}
‌‌‌‌‌case 'L' -> {
‌‌‌‌‌‌lx = x;
‌‌‌‌‌‌ly = y;
‌‌‌‌‌}
‌‌‌‌‌case 'E' -> {
‌‌‌‌‌‌ex = x;
‌‌‌‌‌‌ey = y;
‌‌‌‌‌}
‌‌‌‌}
‌‌‌}
‌‌}
‌‌
‌‌int toL = bfs(maps, sx, sy, lx, ly);
‌‌if (toL <= -1) return -1;
‌‌int toE = bfs(maps, lx, ly, ex, ey);
‌‌if (toE <= -1) return -1;
‌‌return toL + toE;
‌}
‌
‌public int bfs(String[] maps, int bx, int by, int gx, int gy)
‌{
‌‌int[] dx = { 0, 1, 0, -1 };
‌‌int[] dy = { -1, 0, 1, 0 };
‌‌int h = maps.length;
‌‌int w = maps[0].length();
‌‌int x = bx, y = by;
‌‌boolean[][] visited = new boolean[h][w];
‌‌
‌‌Queue<Node> q = new LinkedList<>();
‌‌q.offer(new Node(x, y, 0));
‌‌visited[y][x] = true;
‌‌
‌‌while (!q.isEmpty())
‌‌{
‌‌‌Node n = q.poll();
‌‌‌if (n.x == gx && n.y == gy)
‌‌‌‌return n.cost;
‌‌‌for (int i = 0; i < 4; ++i)
‌‌‌{
‌‌‌‌int nx = n.x + dx[i];
‌‌‌‌int ny = n.y + dy[i];
‌‌‌‌if (nx < 0 || ny < 0 || nx >= w || ny >= h)
‌‌‌‌‌continue;
‌‌‌‌char[] s = maps[ny].toCharArray();
‌‌‌‌char c = s[nx];
‌‌‌‌if (!visited[ny][nx] && 'X' != c)
‌‌‌‌{
‌‌‌‌‌visited[ny][nx] = true;
‌‌‌‌‌q.offer(new Node(nx, ny, n.cost + 1));
‌‌‌‌}
‌‌‌}
‌‌}
‌‌
‌‌return -1;
‌}
}