백준 2178 미로 탐색

백준 2178 미로 탐색

1. 문제 링크

https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

 

2. 문제 해결에 대한 아이디어

1. 2차원 배열로 생각했을 때, 좌측 끝 상단에서 우측 끝 하단으로 이동한다.

2. 따라서 (0, 0)에서 (N-1, M-1)로 이동한 것으로 구현했다.

3. 지나야 하는 칸의 개수를 세기 위해 방문 배열은 int로 구현했다.

4. 현재 칸의 가중치는 이전 칸의 가중치의 + 1로 기록한다.

5. 가중치가 기록되어있는 visited 배열 중, visited [N-1][M-1]에 있는 가중치를 출력한다.

 

3. 코드

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

public class Main {

	static int[][] arr;
	static int[][] weight;
	static boolean[][] visited;
	static int[] di = { 0, 0, 1, -1 };
	static int[] dj = { 1, -1, 0, 0 };
	static int N, M;

	static class Pair {
		int i, j;

		public Pair(int i, int j) {
			super();
			this.i = i;
			this.j = j;
		}

	}

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

		st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		arr = new int[N][M];
		weight = new int[N][M];
		visited = new boolean[N][M];

		for (int i = 0; i < N; i++) {
			String[] line = br.readLine().split("");
			for (int j = 0; j < M; j++) {
				arr[i][j] = Integer.parseInt(line[j]);
			}
		}

		Queue<Pair> q = new LinkedList<>();
		q.add(new Pair(0, 0));
		visited[0][0] = true;
		weight[0][0] = 1;

		while (!q.isEmpty()) {
			Pair now = q.poll();

			for (int k = 0; k < 4; k++) {
				int ii = now.i + di[k];
				int jj = now.j + dj[k];

				if (ii < 0 || ii >= N || jj < 0 || jj >= M 
						|| visited[ii][jj] || arr[ii][jj] != 1)
					continue;

				visited[ii][jj] = true;
				weight[ii][jj] = weight[now.i][now.j] + 1;
				q.add(new Pair(ii, jj));
			}

		}

		System.out.println(weight[N - 1][M - 1]);
	}
}

 

4. 채점 결과

 

5. 느낀 점

1. 가장 기본적인 BFS 문제여서 어려움이 없었다.

2. 방문 배열을 int로 선언하는 것만 신경 쓰면 되는 문제였다.