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

참고 문서

• Programmers: 미로 탈출

이 문서의 내용

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

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

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

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

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

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을 리턴합니다.

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를 실행하여 문제의 결과를 도출합니다.

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: 전체 코드

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

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;
	}
}