[백준 2206번][Java] 벽 부수고 이동하기 - 3차원 BFS 이해하기

www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

이 문제를 제대로 이해하려면 기존의 기본적인 BFS 개념에 차원을 하나 더해야됩니다.

 

지도 위에 두 개의 층이 있다고 생각할 수 있습니다. 하나는 벽을 부수지 않은 경로를 표시하는 지도, 하나는 벽을 부수고 이동하는 경로를 나타내는 지도. 아래의 그림을 보면 쉽게 이해할 수 있을겁니다.

 

 

대부분의 간단한  BFS 예제들은 행렬 상의 2차원 평면에서 움직이지만, 이 문제는 벽을 부쉈는지 여부에 따라 경로들을 따로 생각해줘야 되기 때문에 3차원으로 생각해야 됩니다.

 

뭔가 거창해보이지만 다행히도 기본적인 구현은 크게 달라지지 않습니다.

여전히 하나의 큐를 이용해서 위를 구현할 수 있습니다. 그러기 위해서는 Node 라는 객체가 벽을 부쉈는지 여부(앞으로 이를 breakable 이라는 플래그라고 정의합시다)를 상태로 저장해야 합니다. 이것만으로도 큐에 담긴 노드들이 벽을 부쉈는지 여부에 따라 계층이 나눠지는 효과를 낼 수 있습니다.

 

로직은 다음과 같습니다.

 

if) 다음 방문 가능한 노드의 값이 1인 경우

1. 현재 노드가 breakable == true라면 해당 노드를 큐에 넣고 discovered[r][c][1](벽을 부수는 경로의 방문캐시)에 true를 할당합니다.

2. 현재 노드가 breakable == false 라면 벽을 지나갈 수 없으므로 아무것도 해주지 않아도 됩니다.

 

if) 다음 방문 가능한 노드의 값이 0인 경우

1. 현재 노드가 breakable == true라면 해당 노드를 큐에 넣고 discovered[r][c][1]에 방문 체크

2. 현재 노드가 breakable == false라면 해당 노드를 큐에 넣고 discovered[r][c][0]에 방문 체크

 

 

import java.io.*;
import java.util.*;

/*
벽 부수고 이동하기
https://www.acmicpc.net/problem/2206
 */
public class Main {
	public static void main(String[] args) throws IOException {
		InputReader reader = new InputReader();
//		InputReader reader = new InputReader("testcase.txt");
		StringTokenizer st = new StringTokenizer(reader.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int[][] board = new int[n][m];

		for (int i = 0; i < n; i++) {
			String rowLine = reader.readLine();
			for (int j = 0; j < m; j++) {
				board[i][j] = rowLine.charAt(j)-48;
			}
		}
		boolean[][][] discovered = new boolean[n][m][2];
		int ret = solve(board,discovered);
		System.out.println(ret);
	}

	static int[] dr = {1,-1,0,0};
	static int[] dc = {0,0,1,-1};
	private static int solve(int[][] board, boolean[][][] discovered) {
		int n = board.length; int m = board[0].length;
		Queue<Node> q = new ArrayDeque<>();
		q.add(new Node(Point.create(0,0)));
		discovered[0][0][0] = true;

		while(!q.isEmpty()) {
			Node here = q.poll();
			//종결 조건
			if(here.position.equals(Point.create(n-1, m-1))) return here.distance;

			for (int i = 0; i < 4; i++) {
				int nextRow = here.position.row + dr[i]; int nextCol = here.position.col + dc[i];
				if(isRange(nextRow, nextCol, board)) {
					int nextVal = board[nextRow][nextCol];
					if(nextVal == 1) {
						if(here.canBreakWall && !discovered[nextRow][nextCol][1]) {
							Node nextNode = new Node(Point.create(nextRow, nextCol), here.distance+1, false);
							discovered[nextRow][nextCol][1] = true;
							q.add(nextNode);
						}
					}

					if(nextVal == 0) {
						if(here.canBreakWall && !discovered[nextRow][nextCol][0]) {
							Node nextNode = new Node(Point.create(nextRow, nextCol), here.distance+1, true);
							discovered[nextRow][nextCol][0] = true;
							q.add(nextNode);
						}

						if(!here.canBreakWall && !discovered[nextRow][nextCol][1]) {
							Node nextNode = new Node(Point.create(nextRow, nextCol), here.distance+1, false);
							discovered[nextRow][nextCol][1] = true;
							q.add(nextNode);
						}
					}

				}
			}
		}
		return -1;
	}

	private static boolean isRange(int row, int col, int[][] board) {
		int n = board.length; int m = board[0].length;
		if(row < 0 || row >= n || col < 0 || col >= m) return false;
		return true;
	}
}
class Node {
	Point position;
	int distance;
	boolean canBreakWall;
	public Node(Point position){
		this(position, 1, true);
	}

	public Node(Point position, int distance, boolean canBreakWall) {
		this.position = position;
		this.distance = distance;
		this.canBreakWall = canBreakWall;
	}
}
class Point {
	int row, col;
	private Point(int row, int col) {
		this.row = row;
		this.col = col;
	}
	static Point create(int row, int col) {
		return new Point(row, col);
	}

	@Override
	public boolean equals(Object obj) {
		Point other = (Point) obj;
		if(this.row == other.row && this.col == other.col) return true;
		return false;
	}
}
class InputReader {
	private BufferedReader br;

	public InputReader() {
		br = new BufferedReader(new InputStreamReader(System.in));
	}

	public InputReader(String filepath) {
		try {
			br = new BufferedReader(new FileReader(filepath));
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		}
	}

	public List<Character> readLineIntoCharList() throws IOException {
		List<Character> l = new ArrayList<>();
		while(true) {
			int readVal = br.read();
			if(readVal == '\n' || readVal == -1) break;
			l.add((char)readVal);
		}
		return l;
	}

	public boolean ready() throws IOException {
		return br.ready();
	}

	public String readLine() throws IOException {
		return br.readLine();
	}
	public int readInt() throws IOException {
		return Integer.parseInt(readLine());
	}
	public Long readLong() throws IOException {
		return Long.parseLong(readLine());
	}
}