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

[2206 벽 부수고 이동하기]

난이도: 골드4

2206번: 벽 부수고 이동하기

문제

입력

출력

---

[아이디어]

빠르게 목적지에 도착하는 경우를 구해야하기 때문에 BFS를 활용하면 된다. 하지만 벽을 한 번 파괴할 수 있으므로 파괴한적이 있는지 따로 체크해주며 돌아준다.

그래서 Point 클래스를 따로 만들어주고, 안에는 위치와 이동한 횟수, 파괴했는지를 저장해준다.

static class Point {
    int r, c, cnt;
    boolean distroyed; // 파괴한적이 있는가?

    public Point(int r, int c, int cnt, boolean distroyed) {
        this.r = r;
        this.c = c;
        this.cnt = cnt;
        this.distroyed = distroyed;
    }
}

 

그리고 해당 위치를 방문했는지 체크해주는 배열을 만들어주었는데, 파괴한 횟수가 0번인지 1번인지에 따라 다르게 체크해주어야 하기 때문에 3차원 배열로 만들었다.

마지막으로 BFS를 돌면서 벽을 만났을 때와 벽이 아닌 경우를 다르게 체크해주며 수행해주면 된다!

---

[JAVA 코드]

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 Main {

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tokens;
	
	static int N, M;
	static boolean [][] map;
	static boolean [][][] visited;
	static int [] dr = {-1, 0, 1, 0}, dc = {0, 1, 0, -1};
	
	static class Point {
		int r, c, cnt;
		boolean distroyed; // 파괴한적이 있는가?
		
		public Point(int r, int c, int cnt, boolean distroyed) {
			this.r = r;
			this.c = c;
			this.cnt = cnt;
			this.distroyed = distroyed;
		}
	}
	
	public static void main(String[] args) throws IOException {
		
		tokens = new StringTokenizer(br.readLine());
		N = Integer.parseInt(tokens.nextToken());
		M = Integer.parseInt(tokens.nextToken());
		
		map = new boolean[N][M]; 
		visited = new boolean[N][M][2]; // 마지막 차원 -> 0: 부순적 x, 1: 부순적 o 
		for(int r = 0; r < N; r++) {
			String line = br.readLine();
			for(int c = 0; c < M; c++) {
				if(line.charAt(c) == '0') {
					map[r][c] = true;
				}
			}
		}
		
		Queue<Point> Q = new LinkedList<>();
		Q.offer(new Point(0, 0, 1, false)); // 0, 0 위치 넣기
		visited[0][0][0] = true;
		
		while(!Q.isEmpty()) {
			Point p = Q.poll();
			
			// 목적지 도착
			if(p.r == N - 1 && p.c == M - 1) {
				System.out.println(p.cnt);
				return;
			}
			
			for(int i = 0; i < 4; i++) {
				int nr = p.r + dr[i];
				int nc = p.c + dc[i];
				int ncnt = p.cnt + 1;
				
				if(nr < 0 || nr >= N || nc < 0 || nc >= M) continue; // 인덱스 벗어남
				if(map[nr][nc] == false && p.distroyed) continue; // 벽을 만났는데 이미 부순 후라면
				
				if(map[nr][nc]) { // 벽이 아니라면
					if(!p.distroyed && !visited[nr][nc][0]) {
						Q.offer(new Point(nr, nc, p.cnt + 1, false));
						visited[nr][nc][0] = true;
					} else if(p.distroyed && !visited[nr][nc][1]) {
						Q.offer(new Point(nr, nc, p.cnt + 1, true));
						visited[nr][nc][1] = true;
					}
				} else { // 벽이라면
					if(!p.distroyed) {
						Q.offer(new Point(nr, nc, p.cnt + 1, true));
						visited[nr][nc][1] = true;
					}
				}
				
			}
		}
		
		// 끝까지 가지 못한 경우
		System.out.println("-1");
	}
	
	

}