[백준/java] 2206번: 벽 부수고 이동하기 - BFS

2206번: 벽 부수고 이동하기

728x90

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

2206번: 벽 부수고 이동하기

 

지금까지 내가 풀어본 BFS 문제 중에 가장 어려웠던 문제였다.

 

그냥 기존에 풀던 방법대로 풀다가는 풀리지 않는다.

 

특히나, 기존에 입력한 int형 2차원 배열 값을 변경해서는 결코 안된다.

 

반응형

지문을 읽다보면 벽이 있을 때, 벽을 한번은 부술 수 있는 기회가 주어진다.

그렇다고 해서 map[ny][nx] = 0; 으로 값을 바꿔버리면 제출했을 때 오답이 된다.

정답을 찾기위해 가야될 방향이 달라질 수도 있기 때문이다.

 

그러면 어떻게 해야할까?

 

visit을 3차원 배열로 바꿔주어서

벽을 아직 안만났을 때는 visit[destroy==1][y][x],

벽을 만났을 때는 visit[destroy==0][y][x]로 처리를 해주면 된다.

 

package bfs;

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 DestroyWallAndMove {
	static int[] dy = {1, 0, -1, 0};
	static int[] dx = {0, 1, 0, -1};
	static int[][] map;
	static boolean [][][] visit;
	static int N, M;
	static class Node {
		int y, x, destroy, distance;
		public Node(int y, int x, int destroy, int distance) {
			this.x = x;
			this.y = y;
			this.destroy = destroy;
			this.distance = distance;
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = stoi(st.nextToken());
		M = stoi(st.nextToken());
		
		map = new int[N][M];
		visit = new boolean[2][N][M];
		
		for (int i = 0; i < N; i++) {
			String[] arr = br.readLine().split("");
			for (int j = 0; j < M; j++) {
				map[i][j] = stoi(arr[j]);
			}
		}
		
		System.out.println(bfs());
	}
	
	public static int bfs() {
		Queue<Node> q = new LinkedList<Node>();
		q.add(new Node(0, 0, 1, 1));
		while(!q.isEmpty()) {
			Node cur = q.poll();
			
			if(visit[cur.destroy][cur.y][cur.x]) continue;
//			if(cur.destroy == 0 && map[cur.y][cur.x] == 1) continue;
			visit[cur.destroy][cur.y][cur.x] = true;
			
			if(cur.y == N-1 && cur.x == M-1) {
				return cur.distance;
			}
			
			for (int dir = 0; dir < 4; dir++) {
				int ny = cur.y + dy[dir];
				int nx = cur.x + dx[dir];
				int destroy = cur.destroy;
				
				if(ny < 0 || ny >= N || nx < 0 || nx >= M) continue;
				if(visit[destroy][ny][nx]) continue;
				if(map[ny][nx] != 0) {
					if(destroy == 0) continue;
					destroy--;
                    // 값을 바꿔주면 오답처리가 된다.
                    // 방향을 바꿔서 원래 자리로 돌아온 후 다시 다른 방향으로 진행할 때 
                    // 값이 0인 상태가 되버리면 처음 진행되야될 루트와 방향이 달라질 수도 있기
                    // 때문이다.
					// map[ny][nx] = 0;
				}
				
				int distance = cur.distance + 1;
				q.add(new Node(ny, nx, destroy, distance));
			}
		}
		
		return -1;
	}
	
	public static int stoi(String str) {
		return Integer.parseInt(str);
	}
}