백준 2206번 : 벽 부수고 이동하기 자바

🧫 문제 분석

✔️ 출처

백준 2206번 벽 부수고 이동하기 골드 3

 

📖 문제

 

그래프 BFS 탐색 문제이다.

여러가지 방법으로 탐색, 최단 거리로

벽을 부순 경우와 부수지 않은 경우 방문을 체크해줘야한다. 

 

그외에는 단순한 넓이 우선 탐색을 해주면 된다. 

 

조심할 것은 시작지점도 거리에 포함

 

 

비슷한 문제 

백준 1600번 : 말이 되고픈 원숭이 자바

 

 

 

---

🔅 문제 풀이

import java.io.*;
import java.util.*;

public class Main {
    static int[][] graph;
    static boolean[][][] visited;
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        graph = new int[n][m];
        visited = new boolean[n][m][2]; // 벽을 부순 경우 , 안부순 경우

        for (int i = 0; i < n; i++) {
            String line = br.readLine();

            for (int j = 0; j < m; j++) {
                graph[i][j] = line.charAt(j) - '0';
            }
        }

        bw.write(bfs(n - 1,m - 1) + "\n");
        bw.flush();
        bw.close();
    }

    private static int bfs(int r, int c) {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{0,0,1,1}); // r, c , 이동거리, 벽부쉈는지 여부
        visited[0][0][1] = true; // 0 : 벽 부숨, 1 : 안부숨

        while (!q.isEmpty()) {

            int[] poll = q.poll();
            if (r == poll[0] && c == poll[1]) return poll[2];

            for (int i = 0; i < 4; i++) {
                int newY = poll[0] + dy[i];
                int newX = poll[1] + dx[i];
                int count = poll[2];
                int check = poll[3];

                // 범위 및 방문 검증
                if (checkBoundaryAndVisited(newY, newX, check)) continue;

                // 다음이 벽이고, 아직 벽을 안부쉈다면
                if (check == 1 && graph[newY][newX] == 1) check = 0;
                // 다음이 벽이고 벽을 부순적이 있다면
                else if (graph[newY][newX] == 1) continue;

                q.add(new int[] {newY, newX, count + 1, check});
                visited[newY][newX][check] = true;
            }
        }
        return -1;
    }

    private static boolean checkBoundaryAndVisited(int newY, int newX, int check) {
        return newY < 0 || newY >= graph.length
                || newX < 0 || newX >= graph[0].length
                || visited[newY][newX][check];
    }


}

 

 

❗ 오답노트 / 필요한 지식

1.  말이 되고픈 원숭이 문제를 풀고나니 이러한 문제의 유형을 잘 알게되었다. 
2. BFS-다중 경로 탐색 이라고 생각하고 이 유형을 잘 기억해둬야겠다.