[백준] 2206 벽 부수고 이동하기 - BFS + 아이디어 JAVA

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

2206번: 벽 부수고 이동하기

문제풀이

BFS 문제입니다.

이 문제에서 가장 중요한 로직은,

벽을 한번 부순후에는 그 이후에 움직이는 위치의 표시도 벽을 부순것으로 처리해야한다는 것입니다.

즉, 벽을 한번 부순 후에 벽을 부순 Visited[0][0][1] 로 처리하지 않으면,

벽을 1번 뚫고 진행한 경로와 벽을 뚫지않고 진행한 경로가 겹쳐서 문제가 됩니다.

에러나는 예시 케이스입니다.

5 5
00000
11101
00001
01111
00010

여기서 문제점은 (1,0)의 벽을 뚫고서 이동하였을때 만약 이후의 움직이부터 Visited[0][0][1] 로 처리하지 않는다면,

아직 벽을 뚫지않은 노드가 (2,0) -> (2,1) -> (...) 로 이동하는 경로로 가지못하고, 끝의 (4, 3)의 벽을 뚫지 못하여 -1 이 나옵니다.

이 경우에  출력값이 answer처럼 15가 나와야합니다.

출력: -1

answer: 15

 

해당 코드로직입니다. 

//빈 공간이라면
if(map[nx][ny] =='0') {
    //벽을 한번도 부순적이 없다면,
    if(wallbreakflag == false && visited[nx][ny][0] == false) {
        visited[nx][ny][0] = true;	
        q.offer(new Node(nx, ny, cnt+1, wallbreakflag));
    }
    //벽을 부순적이 있다면
    else if(wallbreakflag == true && visited[nx][ny][1] == false){
        q.offer(new Node(nx, ny, cnt+1, wallbreakflag));
        visited[nx][ny][1] = true;
    }
}

여기서보면, 빈공간일때 벽을 부순적이 없다면, 벽을 부순적이 없는 Visited[][][0] 을 사용하고

벽을 부순적이 있다면 그 이후부터는 벽을 부순적이 있다는 Visited[][][1] 을 사용합니다.

해당 사항을 생각하지 못하여서 어려웠던 문제였습니다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
	
	public static int N,M;
	public static char[][] map;
	public static Queue<Node> q = new LinkedList<>();
	public static boolean[][][] visited;
	public static int result=-1;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	M = Integer.parseInt(st.nextToken());

    	map = new char[N][M];
    	visited = new boolean[N][M][2];
    	for(int i=0;i<N;i++) {
    		map[i] = br.readLine().toCharArray();
    	}
    	
    	simulate();
    	System.out.println(result);
    }
    
    public static void simulate() {
    	int[] dx = {-1,1,0,0};
    	int[] dy = {0,0,-1,1};
    	
    	q.offer(new Node(0,0,0,false));
    	visited[0][0][0] = true;
    	
    	while(!q.isEmpty()) {
    		Node temp = q.poll();
    		int x = temp.x;
    		int y = temp.y;
    		int cnt = temp.cnt;
    		boolean wallbreakflag = temp.wallbreakflag;
    		
    		if(x == N -1 && y == M - 1) {
    			result = cnt + 1;
    			return;
    		}
    		for(int dir=0;dir<4;dir++) {
    			int nx = temp.x + dx[dir];
    			int ny = temp.y + dy[dir];
    			
    			if(nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
    			
    			//벽이라면 벽을 부술 수 있는지 없는지 확인해야합니다.
    			if(map[nx][ny] =='1' && visited[nx][ny][1] == false) {
    				//벽을 이전에 부순적이 없다면 
    				 if(wallbreakflag == false) {
     					q.offer(new Node(nx, ny, cnt+1, true));
     					visited[nx][ny][1] = true;
     				}
    				//벽을 이전에 부순적이 있다면 false
    				 else if(wallbreakflag == true) {
    					continue;
    				}
    			}

				//빈 공간이라면
    			if(map[nx][ny] =='0') {
					//벽을 한번도 부순적이 없다면,
    				if(wallbreakflag == false && visited[nx][ny][0] == false) {
    					visited[nx][ny][0] = true;	
        				q.offer(new Node(nx, ny, cnt+1, wallbreakflag));
    				}
                    //벽을 부순적이 있다면
                    else if(wallbreakflag == true && visited[nx][ny][1] == false){
        				q.offer(new Node(nx, ny, cnt+1, wallbreakflag));
    					visited[nx][ny][1] = true;
    				}
    			}
    		}
    	}
    }
    
    
}

class Node{
	int x;
	int y;
	int cnt;
	boolean wallbreakflag;
	public Node(int x, int y, int cnt,boolean wallbreakflag) {
		this.x=x;
		this.y=y;
		this.cnt = cnt;
		this.wallbreakflag = wallbreakflag;
	}
}