[백준(Baekjoon)][자바(java)] 2178 : 미로 탐색 / 그래프와 순회

 

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

2178번: 미로 탐색

 

문제 풀이

 

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 {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken()),
			m = Integer.parseInt(st.nextToken()), map[][] = new int[n][m], i, j, d;
		String s;
		for (i = 0; i < n; ++i) {
			s = br.readLine();
			for (j = 0; j < m; ++j)
				map[i][j] = s.charAt(j) - '0';
		}
		br.close();

		int cnt = 0, dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0}, pos[], x, y, c, nx, ny, nc;
		boolean visited[][] = new boolean[n][m];
		visited[0][0] = true;
		Queue<int[]> queue = new LinkedList<>(); // x, y, cnt
		queue.add(new int[]{0, 0, 1});
		while (!queue.isEmpty()) {
			pos = queue.remove();
			x = pos[0];
			y = pos[1];
			c = pos[2];
			if (x == n - 1 && y == m - 1) {
				cnt = c;
				break;
			}
			nc = c + 1;
			for (d = 0; d < 4; ++d) {
				nx = x + dx[d];
				ny = y + dy[d];
				if (nx < 0 || nx >= n || ny < 0 || ny >= m || 
					map[nx][ny] == 0 || visited[nx][ny])
					continue;
				visited[nx][ny] = true;
				queue.add(new int[]{nx, ny, nc});
			}
		}
		
		System.out.println(cnt);
	}
}