[백준(Baekjoon)][자바(java)] 2206 : 벽 부수고 이동하기 / 그래프와 순회

 

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

2206번: 벽 부수고 이동하기

 

문제 풀이

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String[] args) throws Exception {
		
		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());
		int map[][] = new int[n][m], i, j; String str;
		for (i = 0; i < n; ++i) {
			str = br.readLine();
			for (j = 0; j < m; ++j)
				map[i][j] = str.charAt(j) - '0';
		}
		br.close();
		
		final int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0},
					x_start = 0, y_start = 0,
					x_end = n - 1, y_end = m - 1;
		
		Deque<int[]> queue = new ArrayDeque<>(); // x, y, distance, is_broken (0:false, 1:true)
		queue.add(new int[] {x_start, y_start, 1, 0});
		
		boolean[][][] visited = new boolean[n][m][2]; /* 부술 수 있는 벽을 부순 경우와 안 부순 경우를 각각 나눔 */
		visited[x_start][y_start][0] = visited[x_start][y_start][1] = true;
		
		int answer = -1, cell[], x, y, distance, broken, x_next, y_next, distance_next, broken_next;
		while (!queue.isEmpty()) {
			cell = queue.remove();
			x = cell[0];
			y = cell[1];
			distance = cell[2];
			if (x == x_end && y == y_end) {
				answer = distance;
				break;
			}
			broken = cell[3];
			distance_next = distance + 1;
			for (i = 0; i < 4; ++i) {
				x_next = x + dx[i];
				y_next = y + dy[i];
				if (x_next < 0 || x_next >= n || y_next < 0 || y_next >= m || visited[x_next][y_next][broken])
					continue;
				broken_next = broken;
				if (map[x_next][y_next] == 1) {	/* 다음 칸이 벽 */
					if (broken == 1) continue;	/* 〃 이고 이미 한 번 부순 경우는 pass */
					broken_next = 1;				/* 〃 이고 벽을 부순 적 없는 경우 벽을 부숨 */
				}
				queue.add(new int[] {x_next, y_next, distance_next, broken_next});
				visited[x_next][y_next][broken_next] = true;
			}
		}
		
		System.out.println(answer);
	}
}