백준 2206 벽 부수고 이동하기 (Java)

1. 문제 링크

2206번: 벽 부수고 이동하기

 

2. 문제 및 입출력예제

+) 반례 테스트케이스 모았습니다. 참고하세요~

2 4
0111
0010
ans: 5
---
2 4
0111
0110
ans: -1
---
1 1
0
ans: 1
---
5 8
01000000
01010000
01010000
01010011
00010010
ans: 20
---
6 7
0000000
0111111
0100010
0101010
0101010
0001010
ans: 12
---
8 8
01000100
01010100
01010100
01010100
01010100
01010100
01010100
00010100
ans: 29
---
3 3
011
111
110
ans: -1
---
3 6
010000
010111
000110
ans: 12
---
3 3
000
000
000
ans: 5
---
4 4
0101
0101
0001
1110
ans: 7

 

3. 문제 풀이

1. map이 0과 1로만 이루어져 있어서 boolean 배열로 만들었다.
2. bfs를 이용해 N, M에 도착할 때까지 반복하여 최단거리를 구한다.
3. int[] 은 x좌표, y좌표, 거리, 벽을 뚫고 왔는지 유무를 담았다.
4. 범위 안에서 벽이 아니라면, 방문 여부만 파악하고 큐에 넣는다.
5. 범위 안에서 벽이라면, 지금까지 벽을 안 뚫고 왔는지와 벽을 뚫은 상태로 방문했는지 파악하고 큐에 넣는다.

 

4. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;

public class Main {
	static int N, M;
	static long result;
	static boolean[][] map, visit[];
    public static void main(String[] args) throws IOException{
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       String[] split = br.readLine().split(" ");
       N = Integer.parseInt(split[0]);
       M = Integer.parseInt(split[1]);
       map = new boolean[N+1][M+1];
       visit = new boolean[N+1][M+1][2];
       for(int i=1;i<N+1;i++) {
    	   String str = br.readLine();
    	   for(int j=1;j<M+1;j++) {
    		   if(str.charAt(j-1)=='0') {
    			   map[i][j] = true;
    		   }
    		   else {
    			   map[i][j] = false;
    		   }
    	   }
       }
       bfs(1,1);
       System.out.println(result);
	}
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
	private static void bfs(int x, int y) {
		Queue<int[]> queue = new ArrayDeque<int[]>();
		queue.offer(new int[] {x, y, 1, 0});
		visit[x][y][0] = true;
		int count = 0;
		boolean flag = false;
		int[] temp;
		while(!queue.isEmpty()) {
			temp = queue.poll();
			if(temp[0]==N && temp[1]==M) {
				flag = true;
				count = temp[2];
				break;
			}
			for(int d=0;d<4;d++) {
				int X = temp[0]+dx[d];
				int Y = temp[1]+dy[d];
				if(X>0 && X<=N && Y>0 && Y<=M ) {
					if(map[X][Y]) {
						if(!visit[X][Y][temp[3]])
						queue.offer(new int[] {X, Y, temp[2]+1, temp[3]});
						visit[X][Y][temp[3]] = true;
					}
					else {
						if(temp[3]==0 && !visit[X][Y][1]) {
							queue.offer(new int[] {X, Y, temp[2]+1, 1});
							visit[X][Y][1] = true;
						}
					}					
				}
			}
		}
		if(flag) result = count;
		else result = -1;
	}
}