[백준] 2206 벽 부수고 이동하기

📌 문제

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.

만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다.

한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.

✔ 접근방법

최단거리를 구하는 문제이기 때문에 BFS를 사용한다.

BFS를 이용하면 비교적 어렵지 않게 문제풀이를 할 수 있다고 생각했으나 생각보다 시간이 오래걸린 문제였다.

포인트는 방문을 체크하는 visit배열의 좌표값과 벽을 부섰는지를 체크하는 값을 함께 담아야 한다는 것이다.

같은 좌표를 접근하더라도 벽을 부수고 왔는지, 아닌지에 따라서 다음으로 이동할 수 있는 길이 달라지기 때문이다.

✔ 코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class qnode {
	int x;
	int y;
	boolean check; // 벽 부셨는지
	int count;

	public qnode(int x, int y, boolean check, int count) {
		this.x = x;
		this.y = y;
		this.check = check;
		this.count = count;
	}
}

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		int[][] map = new int[n][m];
		boolean[][][] visit = new boolean[n][m][2];
		Queue<qnode> q = new LinkedList<>();
		int[] dx = { -1, 0, 1, 0 };
		int[] dy = { 0, 1, 0, -1 };
		for (int i = 0; i < n; i++) {
			String Line = sc.next();
			for (int j = 0; j < m; j++) {
				map[i][j] = Line.charAt(j);
			}
		}

		q.offer(new qnode(0, 0, false, 1));
		visit[0][0][0] = true;
		int answer = 1000000;
		while (!q.isEmpty()) {
			qnode cur = q.poll();
			int cx = cur.x;
			int cy = cur.y;
			int checkCount = 0;
			boolean check = cur.check;
			int curCount = cur.count + 1;

			if (check)
				checkCount = 1;

			if (cx == n - 1 && cy == m - 1) {
				answer = Math.min(answer, curCount - 1);
				continue;
			}
			

			// 방향 4개 이동
			for (int i = 0; i < 4; i++) {
				int nx = cx + dx[i];
				int ny = cy + dy[i];

				if (nx < 0 || nx >= n || ny < 0 || ny >= m)
					continue;
				if (visit[nx][ny][checkCount])
					continue;

				if (map[nx][ny] == '1' && !check) { // 벽이고 아직 벽을 안부셨으면
					visit[nx][ny][1] = true; // 방문표시
					q.offer(new qnode(nx, ny, true, curCount)); // 벽을 부시고 넣음
				}
				if (map[nx][ny] == '0') {
					visit[nx][ny][checkCount] = true;
					q.offer(new qnode(nx, ny, check, curCount));
				}
			}
		}

		if (answer == 1000000)
			answer = -1;
		System.out.println(answer);

	}
}

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