[백준/2178/Java] 미로탐색 - BFS 풀이

문제

www.acmicpc.net/problem/2178

2178번: 미로 탐색

 

 

 

 

문제를 먼저 풀고 오신 다음에 풀이를 보시는 것을 추천드립니다.

이 문제의 풀이는 BFS/DFS 외에도 다양한 방법이 있을 수 있으며 제가 보여드리는 풀이는 그 중 하나입니다.

 

문제분석

1은 이동할 수 있는 칸이고, 0은 이동할 수 없는 칸입니다.

(1, 1)에서 출발하여 (N, M) 위치로 이동할 때 지나야 하는 최소 칸 수를 구해야 합니다.

 

입력

첫째 줄에 N, M이 주어집니다. (2 <= N, M <= 100)

 

두번째 줄부터 미로 정보가 주어집니다.

N개의 줄에 M개의 정수가 주어집니다.

 

출력

최소 칸수를 출력합니다.

항상 도착위치에 도착할 수 있도록 입력이 주어지므로 그 외 값을 생각하실 필요는 없습니다.

 

풀이

미로의 크기와 동일한 2차원 배열을 생성하고 방문정보를 저장합니다. 방문 배열이라고 칭하겠습니다.

방문 배열에 이동할 때마다 이동칸수를 하나씩 증가하면서 저장하겠습니다.

최소칸수를 구하는 것이므로 이미 방문한 적이 있는 칸은 더 이상 이동할 필요가 없습니다.

시작지점인 (1, 1)도 칸이므로 칸수가 1입니다.

따라서, 방문 배열에 1부터 시작해서 (N, M)에 도착했을 때의 값을 출력하면 됩니다.

 

예제풀이

백준온라인에 나온 예제들을 Input(미로)와 Output(정답, 방문배열)로 표시해보겠습니다.

 

Input#1

4 6
101111
101010
101011
111011

 

OutPut#1

길이 하나 밖에 없으므로 길을 따라가면 답은 15가 나옵니다.

15

//방문배열
[1, 0, 9, 10, 11, 12]
[2, 0, 8, 0, 12, 0]
[3, 0, 7, 0, 13, 14]
[4, 5, 6, 0, 14, 15]

 

Input#2

4 6
110110
110110
111111
111101

Output#2

인접한 칸이 있어서 물에서 파동을 일으키면 번져나가듯이 됩니다.

9

//방문배열
[1, 2, 0, 8, 9, 0]
[2, 3, 0, 7, 8, 0]
[3, 4, 5, 6, 7, 8]
[4, 5, 6, 7, 0, 9]

 

Input#3

7 7
1011111
1110001
1000001
1000001
1000001
1000001
1111111

 

Output#3

둘 중에 2번째 이동한 칸에서 오른쪽과 아래쪽으로 이동하는 갈림길이 생깁니다.

(N, M)에 먼저 도착하는 길에서 먼저 13을 설정하고 늦게 도착한 길에서 더 이상 덮어쓰지 않습니다.

13

//방문배열
[1, 0, 5, 6, 7, 8, 9]
[2, 3, 4, 0, 0, 0, 10]
[3, 0, 0, 0, 0, 0, 11]
[4, 0, 0, 0, 0, 0, 12]
[5, 0, 0, 0, 0, 0, 13]
[6, 0, 0, 0, 0, 0, 14]
[7, 8, 9, 10, 11, 12, 13]

 

알고리즘 문제를 풀 때 이와 같이 방문배열을 출력하면 중간에 if 조건을 잘못 적었다 하더라도

생각하는 값과 눈으로 확인하는 값이 다르므로 그 부분부터 추적해서 잘못된 소스를 고칠 수 있습니다.

 

소스

배열 2개를 선언해서 하나는 미로 정보를 저장하고 다른 하나는 방문 정보를 저장합니다.

방문 배열을 확인하시고 싶으신 분은 주석을 해제하고 돌려보시기 바랍니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main
{
	static int N;
	static int M;
	static int d[][];

	static int v[][];

	public static void main(String[] args) throws Exception
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String input = br.readLine();

		StringTokenizer st = new StringTokenizer(input);

		N = Integer.valueOf(st.nextToken());
		M = Integer.valueOf(st.nextToken());

		d = new int[N][M];
		v = new int[N][M];

		for (int i = 0; i < N; i++)
		{
			input = br.readLine();
			for (int j = 0; j < M; j++)
			{
				d[i][j] = input.charAt(j);
			}
		}

		bfs(0, 0);

		System.out.println(v[N - 1][M - 1]);
		
//		System.out.println("\n//방문배열");
//		for (int i = 0; i < N; i++) {
//			System.out.println(Arrays.toString(v[i]));
//		}
	}

	private static void bfs(int i, int j)
	{
		Queue<Integer> queue = new LinkedList<Integer>();

		queue.offer(i * 100 + j);
		v[0][0] = 1;

		int pos = 0;
		while (queue.isEmpty() == false)
		{
			pos = queue.poll();
			i = pos / 100;
			j = pos % 100;

			if (i > 0 && d[i - 1][j] == '1' && v[i - 1][j] == 0)
			{
				v[i - 1][j] = v[i][j] + 1;
				queue.offer((i - 1) * 100 + j); // 상
			}
			if (i < N - 1 && d[i + 1][j] == '1' && v[i + 1][j] == 0)
			{
				v[i + 1][j] = v[i][j] + 1;
				queue.offer((i + 1) * 100 + j); // 하
			}
			if (j > 0 && d[i][j - 1] == '1' && v[i][j - 1] == 0)
			{
				v[i][j - 1] = v[i][j] + 1;
				queue.offer(i * 100 + (j - 1)); // 좌
			}
			if (j < M - 1 && d[i][j + 1] == '1' && v[i][j + 1] == 0)
			{
				v[i][j + 1] = v[i][j] + 1;
				queue.offer(i * 100 + (j + 1)); // 우
			}
		}
	}
}

 

관련글:

2021/01/28 - [Algorithm] - [백준/BOJ/7576] 토마토 - BFS 풀이

[백준/BOJ/7576] 토마토 - BFS 풀이

 

 

2021/01/21 - [Algorithm] - [백준/BOJ/1697] 숨바꼭질 - BFS 풀이

[백준/BOJ/1697] 숨바꼭질 - BFS 풀이