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

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

2206번: 벽 부수고 이동하기

---

길찾기라서 BFS라는건 바로 알았는데....

벽 부수기 처럼 변수가 있는 문제는 저번에도 한 번 못푼 적이 있다

아마 어디 코테 볼 때 나왔던 거 같은데,,,,

암튼 갑자기 그 때 생각이 나서 풀어봤는데 겨우 이해했다,,,,

 

---

우선 이 문제에서는 벽을 최대 한번 부술 수 있기 때문에 BFS를 통해 탐색하면서 현재까지 벽을 부순적이 있는지에 대한 여부를 확인해줘야 한다

이를 확인하기 위해서 Point 클래스를 만들었다

Point 클래스에는 x좌표, y좌표, 현재 위치까지 방문한 노드의 수(count), 벽 부순 여부(crash)가 있다

그리고 visit 배열도 3차원 배열로 선언하였다

visit[x][y][0]은 현재까지 벽을 부수지 않고 진행했다는 것이고, visit[x][y][1]은 벽을 부순적이 있다는 것이다

visit 배열을 둘 중 어떤것을 선택할지는 Point 클래서의 crash에 따라서 결정하였다

 

그리고 나머지는 똑같다

그냥 BFS 돌리면서 도착지에 도달했으면 현재 answer와 현재 위치의 count 비교해서 최솟값으로 업데이트해준다

이해하기 어려웠던만큼 설명도 어려운데.. 음.. 몇 개 더 풀다보면 확실히 이해될 듯 싶다!!

 

 

 

 

자바 코드)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class boj2206 {
    static boolean[][][] visit;
    static int[][] arr;
    static int answer;

    static class Point {
        int x;
        int y;
        int crash; //벽 부순 여부
        int count; //이동 거리

        public Point(int x, int y, int crash, int count) {
            this.x = x;
            this.y = y;
            this.crash = crash;
            this.count = count;
        }
    }

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

        // 출발지와 도착지가 같은 경우
        if (n - 1 == 0 && m - 1 == 0) {
            System.out.println(1);
            return;
        }

        // visit[x][y][0] : 아직 벽을 부수지 않은 경우
        // visit[x][y][1] : 이미 벽을 부순 경우
        visit = new boolean[n][m][2];
        arr = new int[n][m];

        // map 초기 설정
        for (int i = 0; i < n; i++) {
            String str = br.readLine();
            for (int j = 0; j < m; j++) {
                arr[i][j] = str.charAt(j) - '0';
            }
        }

        answer = Integer.MAX_VALUE; // 답 초기 설정
        bfs(0, 0, n, m); //(0,0)에서 출발

        if (answer == Integer.MAX_VALUE) { //도착지에 갈 수 없는 경우
            System.out.println(-1);
        } else {
            System.out.println(answer);
        }
    }

    private static void bfs(int x, int y, int n, int m) {
        int[] dx = {1, -1, 0, 0}; //상 하 좌 우
        int[] dy = {0, 0, -1, 1};

        Queue<Point> q = new LinkedList<>();
        q.add(new Point(0, 0, 0, 1)); //이동거리가 1인 이유 - 문제 조건에 시작하는 칸도 포함하여 거리를 센다고 함
        visit[0][0][0] = true; //출발지 방문 체크

        while (!q.isEmpty()) {
            Point p = q.poll();

            // 만약 목적지에 도착하면, 지금까지의 이동거리와 answer를 비교해서 최솟값으로 업데이트
            if (p.x == n - 1 && p.y == m - 1) {
                answer = Math.min(answer, p.count);
                continue;
            }

            // 4방향 탐색
            for (int i = 0; i < 4; i++) {
                int nx = p.x + dx[i];
                int ny = p.y + dy[i];

                // 범위 확인
                if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
                    // 이미 방문한 경우 탐색 X
                    if (visit[nx][ny][p.crash]) {
                        continue;
                    }

                    // 벽이 아닌 경우
                    if (arr[nx][ny] == 0) {
                        visit[nx][ny][p.crash] = true;
                        q.add(new Point(nx, ny, p.crash, p.count + 1));
                    } else if (arr[nx][ny] == 1 && p.crash == 0) { //현재 벽인데, 아직 벽을 부순 적이 없는 경우
                        visit[nx][ny][1] = true;
                        q.add(new Point(nx, ny, 1, p.count + 1));
                    }
                }
            }
        }
    }
}

 

 

 

 

---

참고)

https://developer-ellen.tistory.com/92

BOJ - 벽 부수고 이동하기 2206번 (JAVA)