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

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

2206번: 벽 부수고 이동하기

 

<문제 분석>

1. 최단거리 구하기 문제이므로 BFS 탐색을 사용하면 된다.

2. 벽을 한개까지 부술 수 있다. 탐색 시에 벽을 만나도 한번 더 나갈 수 있다는 뜻.

  2-1. 최대 한개까지 1 -> 0으로 바꿀 수 있다.

  2-2. 벽 공사 여부를 변수로 넣고 dist 배열을 dist[N][M][2]개로 만들어서 관리

  2-3. 벽을 한번도 안 뚫은 경우는 dist[][][0]으로 거리 저장, 뚫은 경우는 dist[][][1]에 저장

 

<코드 구현 #1>

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

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

public class Main {
    static int N, M;
    static int map[][];
    static int dist[][][];

    class Point {
        int x, y;
        Point (int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    void InputData() {
        Scanner in = new Scanner(System.in);
        N = in.nextInt();
        M = in.nextInt();
        map = new int[N+1][M+1];
        for (int i=1; i<=N; i++) {
            String str = in.next();
            for (int j=1; j<=M; j++) {
                map[i][j] = str.charAt(j-1)-'0';
            }
        }
    }

    int dx[] = {-1, 0, 1, 0};
    int dy[] = {0, 1, 0, -1};
    void BFS() {
        Queue<Point> Q = new LinkedList<>();
        Q.offer(new Point(1, 1)); // 큐에 시작점 넣기
        dist[1][1][0] = 1; // 방문처리 및 거리 업데이트
        int destoryed = 0;
        int ans = -1;

        while(!Q.isEmpty()) {
            Point tmp = Q.poll(); // 큐에서 하나 꺼내고 삭제함.
            int x = tmp.x;
            int y = tmp.y;
            //System.out.println("x= "+x+", y= "+y+", dist= "+dist[x][y][destoryed]);

            if (x == N && y == M) {
                ans = dist[N][M][destoryed];
                break;
            }
            for (int i=0; i<4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (nx < 1 || nx > N || ny < 1 || ny > M) continue;
                //if (map[nx][ny] == 1) continue;
                if (map[nx][ny] == 0) { // 벽이 아니면
                    if (destoryed == 0 && dist[nx][ny][0] == 0) { // 벽을 부순 적이 없고, 방문한 적이 없으면
                        Q.offer(new Point(nx, ny));
                        dist[nx][ny][0] = dist[x][y][0] + 1;
                    } else if (destoryed == 1 && dist[nx][ny][1] == 0) { // 벽을 부순 적이 있고, 방문한 적이 없으면
                        Q.offer(new Point(nx, ny));
                        dist[nx][ny][1] = dist[x][y][1] + 1;
                    }
                    // 벽을 부순 적이 있으면
                } else { // 벽이면
                    if (destoryed == 0) { // 한번도 부순적이 없다면 부순다.
                        Q.offer(new Point(nx, ny));
                        dist[nx][ny][1] = dist[x][y][0] + 1;
                        destoryed = 1;
                    }
                    // 벽을 부순적이 있다면 스킵한다.
                }

            }
        }    

        System.out.println(ans);

    }
    
    void Solve() throws Exception {
        // dist[][][0] = 벽 부수기 전의 거리 기록용
        // dist[][][1] = 벽 부순 후의 거리 기록용
        dist = new int[N+1][M+1][2];
        BFS();

    }

	public static void main(String[] args) throws Exception {
        Main m = new Main();
        m.InputData();
        m.Solve();
	}
}

<제출 결과 - 실패>

 

<풀이 #2>

1. class Point에 x, y 좌표 뿐만 아니라 거리와 벽 부순 횟수를 가지고 다니도록 구현한다. (미처 생각 못한 부분)

  1-1. 특정 좌표에서 탐색을 할 때 벽을 부수고 온 경우인지 안 부수고 온 경우인지 이전 정점을 보고 판단을 해야 함.

    따라서 전역변수로 벽 부순 횟수를 관리하면 세세한 관리를 할 수가 없음.

2. visited[][]을 boolean이 아니라 int형으로 설정해서 최대값으로 초기화한다.

  2-1. 방문할 정점의 공사횟수가 지금보다 같거나 작다는 것은 벽을 안 부수고 온 쪽에서 이미 탐색을 했다는 것이다.

    그러니, 굳이 벽을 부수고 온 쪽에서 또 탐색을 할 필요가 없다. (벽을 안 부순 쪽이 더 탐색거리가 더 유리할 것이므로)

 

<기억노트>

1. BFS 기본형에 새로운 조건을 추가시켜주는 형태

2. Class 선언 시에 x, y 좌표 뿐만 아니라 정점에서 추가되는 고유의 정보들을 저장해서 가지고 다니기

3. 방문배열을 boolean이 아닌 int형으로 만들어서, 무한대로 초기화하기. 탐색 여부 조건 시 활용하기.

4. BFS 탐색 시에 똑같은 위치를 여러번 탐색 안 하도록 방문배열의 최소값을 계속 가져다는 것을 조건으로 사용하자.

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

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

public class Main {
    static int N, M;
    static int map[][];
    static int visited[][];

    class Point {
        int x, y;
        int distance, drill;
        Point (int x, int y, int distance, int drill) {
            this.x = x;
            this.y = y;
            this.distance = distance;
            this.drill = drill; // 벽 뚫은 횟수
        }
    }
    void InputData() {
        Scanner in = new Scanner(System.in);
        N = in.nextInt();
        M = in.nextInt();
        map = new int[N+1][M+1];
        visited = new int[N+1][M+1];
        for (int i=1; i<=N; i++) {
            String str = in.next();
            for (int j=1; j<=M; j++) {
                map[i][j] = str.charAt(j-1)-'0';
                visited[i][j] = Integer.MAX_VALUE; // 최고값으로 초기화
            }
        }
    }

    int dx[] = {-1, 0, 1, 0};
    int dy[] = {0, 1, 0, -1};
    void BFS() {
        Queue<Point> Q = new LinkedList<>();
        Q.offer(new Point(1, 1, 1, 0)); // 큐에 시작점 넣기
        visited[1][1] = 0; // 처음 공사 횟수        
        int ans = -1;

        while(!Q.isEmpty()) {
            Point tmp = Q.poll(); // 큐에서 하나 꺼내고 삭제함.
            //System.out.println("x= "+x+", y= "+y+", dist= "+dist[x][y][destoryed]);
            if (tmp.x == N && tmp.y == M) {
                ans = tmp.distance;
                break;
            }
            for (int i=0; i<4; i++) {
                int nx = tmp.x + dx[i];
                int ny = tmp.y + dy[i];
                if (nx < 1 || nx > N || ny < 1 || ny > M) continue; // map 범위를 벗어나면 스킵.
                if (visited[nx][ny] <= tmp.drill) continue; // 공사 안한 쪽에서 먼저 탐색했으면 스킵.

                if (map[nx][ny] == 0) { // 벽이 아니면
                    Q.offer(new Point(nx, ny, tmp.distance+1, tmp.drill));
                    visited[nx][ny] = tmp.drill;
                } else { // 벽이면
                    if (tmp.drill == 0) {// 한번도 벽을 부순 적이 없다면 
                        Q.offer(new Point(nx, ny, tmp.distance+1, tmp.drill+1));
                        visited[nx][ny] = tmp.drill+1;
                    }
                    // 벽을 부순적이 있다면 스킵한다.
                }

            }
        }    

        System.out.println(ans);
    }
    
    void Solve() throws Exception {
        BFS();
    }

	public static void main(String[] args) throws Exception {
        Main m = new Main();
        m.InputData();
        m.Solve();
	}
}

 

<풀이 #3>

위 풀이는 코드는 간단하지만 로직이 직관적으로 이해가 되지는 않았다. 그래서 검색을 해보니 방문배열을 3중배열로 사용해서 풀이한 해설을 발견했는데 코드는 더 복잡하지만 오히려 이해가 되었다.

 

예) 5 x 5 배열이 있을 때

0 0 0 0 0

1 1 1 0 1

0 0 0 0 1

0 1 1 1 1

0 0 0 1 0

 

그림으로 표시를 하면

시작점 (1, 1)에서 상/하/좌/우로 너비우선탐색을 시작하면 저렇게 두 갈래로 동시에 탐색을 시작한다.

그런데, 1번 방향으로 탐색하는 경우 (2, 1)의 벽을 부수고 지나가는 경우 (5, 4) 벽 때문에 도착점에 도달을 할 수가 없게 된다.

그렇기 때문에 1번 방향은 정답이 아니게 된다. 하지만 2번 방향으로 진행을 하는 경우 이미 1번 방향으로 지나가면서 방문배열을 true로 만들었기 때문에 지나갈 수가 없게 된다. 따라서 벽을 부수고 진행하는 경우의 방문 배열은 별도로 사용해야 한다.

 

3차원으로 구성한 방문배열 

boolean[][][] visited = new boolean[2][N][M];
visited[0][N][M] // 지금껏 벽을 한번더 부수지 않은 경로의 방문배열
visited[1][N][M] // 벽을 한번 부수고 온 경로의 방문배열

 

벽 부순 것을 기록하는 Node class

class Node {
    int x, y, dist;
    boolean broke;
    Node (int x, int y, int dist, boolean broke) {
        this.x = x;
        this.y = y;
        this.dist = dist; //이동거리
        this.broke = broke; //벽 부순 여부
    }
}

 

탐색지역을 Queue에 넣는 경우의 수

(1) 다음 칸이 벽이 아니면 

    a. 지금까지 벽을 한번도 안 부수고 진행해온 경우

if (!now.broke) { 
    if (visited[0][nx][ny]) continue; // 방문한 곳이면 패스
    visited[0][nx][ny] = true; // 벽 안부순 방문처리
    Q.add(new Node(nx, ny, ndist, false));
}

    b. 벽을 한번 부수고 진행해온 경우

else { 
    if (visited[1][nx][ny]) continue; // 방문한 곳이면 패스
    visited[1][nx][ny] = true; // 벽 부순 방문처리
    Q.add(new Node(nx, ny, ndist, true));
}

(2) 다음 칸이 벽이면

    a. 지금까지 벽을 한번도 안 부수고 진행해온 경우면 부수고 큐에 넣는다.

if (!now.broke) { 
    visited[1][nx][ny] = true; // 벽 부순 방문처리
    Q.add(new Node(nx, ny, ndist, true)); // 벽 부순거 기록
}

    b. 이미 벽을 부쉈으면 패스

 

<코드 #3>

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.Queue;
import java.util.LinkedList;

public class Main {
    static int N, M;
    static int map[][];
    static int min_dist = Integer.MAX_VALUE;
    static boolean visited[][][];
    static boolean found_wall = false;
    static int dx[] = {-1, 0, 1, 0};
    static int dy[] = {0, 1, 0, -1};

    class Node {
        int x, y, dist;
        boolean broke;
        Node (int x, int y, int dist, boolean broke) {
            this.x = x;
            this.y = y;
            this.dist = dist; //이동거리
            this.broke = broke; //벽 부순 여부
        }
    }

    void BFS() {
        Queue<Node> Q = new LinkedList<>();
        Q.add(new Node(1, 1, 1, false)); // 시작점 큐에 넣기
        visited[0][1][1] = true; //
        while(!Q.isEmpty()) {
            Node now = Q.poll();
            // 도착지 도착
            if (now.x == N && now.y == M) {
                System.out.println(now.dist);
                return;
            }
            for (int i=0; i<4; i++) {
                int nx = now.x + dx[i];
                int ny = now.y + dy[i];
                int ndist = now.dist+1;

                // 가지치기
                if (nx<=0 || nx>N || ny<=0 || ny>M) continue; // 맵 범위 벗어나면 패스

                // (1) 벽이 아니면
                // a. 벽을 한번도 안 부수고 진행해온 경우
                // b. 벽을 한번 부수고 진행해온 경우
                if (map[nx][ny] == 0) { 
                    if (!now.broke) { 
                        if (visited[0][nx][ny]) continue; // 방문한 곳이면 패스
                        visited[0][nx][ny] = true; // 벽 안부순 방문처리
                        Q.add(new Node(nx, ny, ndist, false));
                    } else { 
                        if (visited[1][nx][ny]) continue; // 방문한 곳이면 패스
                        visited[1][nx][ny] = true; // 벽 부순 방문처리
                        Q.add(new Node(nx, ny, ndist, true));
                    }
                } else { 
                // (2) 벽이면
                // a. 지금까지 벽을 한번도 안 부수고 진행해온 경우
                // b. 벽을 한번 부수고 진행해온 경우
                    if (!now.broke) { 
                        visited[1][nx][ny] = true; // 벽 부순 방문처리
                        Q.add(new Node(nx, ny, ndist, true)); // 벽 부순거 기록
                    }
                }
            }
        }
        System.out.println(-1);
    }

	void Solve() {
        visited = new boolean[2][N+1][M+1];
        BFS();
	}

    void inputData() throws Exception {
        InputStreamReader reader = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(reader);
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());//열
        M = Integer.parseInt(st.nextToken());//행
        map = new int[N+1][M+1];
        for (int i=1; i<=N; i++) {
            //st = new StringTokenizer(br.readLine());
            String str = br.readLine();
            for (int j=1; j<=M; j++) {
                //map[i][j] = Integer.parseInt(st.nextToken());
                map[i][j] = str.charAt(j-1)-'0';
                if (found_wall != true && map[i][j] == 1) 
                    found_wall = true;
            }
        }
    }

    public static void main(String[] args) throws Exception {
        Main m = new Main();
        m.inputData(); // 입력 받는 부분
        m.Solve();// 여기서부터 작성
    }
}