[백준 2206번] 벽 부수고 이동하기_JAVA

[백준 2206번 벽 부수고 이동하기 URL]

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

[비슷한 유형의 문제]

2019/02/14 - [알고리즘 문제/백준(BOJ)] - [백준 1194번] 달이 차오른다, 가자.

이 문제를 풀기위해서 고려해야할 사항은 다음과 같습니다.

1. 벽을 한번도 부수지 않고 이동하는 경우와 벽을 한번 부수고 이동하는 경로를 따로 체크해야합니다.

2. 2차원 배열 visited가 아닌 3차원 배열 visited[2][row][col]을 선언하여 벽을 부수지 않고 이동하는 경우는 

visited[0][row][col]에 방문체크를 하고 벽 하나를 부수고 이동하는 경우에는 visited[1][row][col]에 방문체크를 

해줍니다.

3. Node 클래스의 jump 멤버가 벽을 부수고 온 경우인지 아닌지 판별하는 변수입니다.

4. 이전에 벽을 부수지 않은 경우(jump == 0)는 2가지로 나뉩니다.

1) 벽을 만났을 경우

벽을 만났을 경우에는 이전에 벽을 부수지 않았으므로 해당 벽을 부수고 이동합니다. (jump를 1로 바꿈)

 2) 벽을 만나지 않았을 경우

벽을 만나지 않았을 경우에는, 그대로 방문처리를 해주고 탐색을 계속합니다.

5. 이전에 벽을 부순 경우(jump == 1)또한 2가지로 나뉩니다.

1) 벽을 만났을 경우

이미 벽을 한번 부쉈으므로 해당 벽을 부술 수 없기 때문에 탐색을 해당 지점에서 종료합니다.

2) 벽을 만나지 않았을 경우

벽을 만나지 않았을 경우에는, 그대로 방문처리를 해주고 탐색을 계속합니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
 
    public static int N, M, ans = Integer.MAX_VALUE;
    public static int[] dirX = new int[] { 0, 0, -1, 1 };
    public static int[] dirY = new int[] { -1, 1, 0, 0 };
    public static int[][] map;
    public static boolean[][][] visited;
 
    public static void main(String[] args) throws Exception {
 
        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 int[N][M];
        visited = new boolean[2][N][M];
 
        for (int i = 0; i < N; i++) {
            String str = br.readLine();
            for (int j = 0; j < M; j++) {
                map[i][j] = Integer.parseInt(str.charAt(j) + "");
            }
        }
        solve();
        if(ans == Integer.MAX_VALUE)
            System.out.println(-1);
        else    
            System.out.println(ans);
    }
 
    public static void solve() {
 
        Queue<Node> q = new LinkedList<Node>();
        q.offer(new Node(0, 0, 1, 0));
 
        while (!q.isEmpty()) {
 
            Node node = q.poll();
            int row = node.row;
            int col = node.col;
            int cnt = node.cnt;
            int jump = node.jump;
 
            if (row == N - 1 && col == M - 1) {
                ans = Math.min(ans, cnt);
                continue;
            }
 
            for (int i = 0; i < 4; i++) {
                int nr = row + dirX[i];
                int nc = col + dirY[i];
 
                if (isBoundary(nr, nc)) {
                    if (jump == 1) {
 
                        if (!visited[jump][nr][nc] && map[nr][nc] == 0) {
                            visited[jump][nr][nc] = true;
                            q.offer(new Node(nr, nc, cnt + 1, jump));
                        }
 
                    } else { // 벽을 안부순 상태
 
                        if (map[nr][nc] == 1) {
                            if (!visited[jump + 1][nr][nc]) {
                                visited[jump + 1][nr][nc] = true;
                                q.offer(new Node(nr, nc, cnt + 1, jump + 1));
                            }
                        } else if (map[nr][nc] == 0) {
                            if (!visited[jump][nr][nc]) {
                                visited[jump][nr][nc] = true;
                                q.offer(new Node(nr, nc, cnt + 1, jump));
                            }
                        }
                    }
                }
 
            }
 
        }
    }
 
    public static boolean isBoundary(int row, int col) {
        return (row >= 0 && row < N) && (col >= 0 && col < M);
    }
}
 
class Node {
 
    int row;
    int col;
    int cnt;
    int jump;
 
    public Node(int row, int col, int cnt, int jump) {
        super();
        this.row = row;
        this.col = col;
        this.cnt = cnt;
        this.jump = jump;
    }
 
}