[백준] no2206: 벽 부수고 이동하기 - 3차원 배열이용 방문

문제

주어진 N x M 사이즈의 맵에서, 0은 통과할 수 있지만, 1은 통과할 수 없는 벽.

단, 1번에 한정해서 벽을 부술 수 있음.

벽을 부수거나 안부수는 경우를 포함하여 최단경로를 구하시오.

 

---

원리

    /**

     * 1. BFS 탐색 진행

     * 2. 객체에 벽을 부술수 있는 능력을 1회 부여

     * 3. 만약 0일경우 통과

     * 4. 만약 1일경우, 능력이 남아 있다면 능력 -1하고 통과

     */

---

풀이방법

기본원리는 다음과 같은 BFS 이다

1. 게임 캐릭터처럼 하나의 객체에 벽을 부술 수 있는 능력 1회 부여
2. BFS를 실행
3. 반복문과 두 개의 좌표용 static 배열을 이용해 상하좌우 좌표이동을 실행
4. 벽(1)일 경우와 벽이아닌(0) 경우를 나눠서 진행
5. 지형이 1일경우, 벽을 부술 기회(chance)가 남아있다면 부수고 다음칸으로 이동
6. 벽을 부술 기회가 없다면 아무런 주취를 취하지 않음
7. 지형이 0일경우, 벽을 부술 기회(chance)가 남아있다면 기회를 유지한채 이동
8. 벽을 부술 기회가 없다면 기회 없는 상태를 유지한채 이동
9. 최단 거리에 도달했을 경우 출력
10. 만약 최단거리가 없는 경우(기존의 최대 min값인 경우) -1 출력

 

1. 필자의 경우 : 객체 클래스 사용

* 이 방법의 경우 채점 18%에서 오답으로 처리된다.

 

2. 레퍼런스의 경우 : 3중 배열 사용

* 이 방법의 차이점은 visited처리에서 3중 배열을 사용함으로써, 벽을 부수고 탐색하는 경우와 부수지 않고 탐색하는 경우를 따로 처리해준다는 점이다.

* 벽을 부수는 경우보다 부수지 않는 편이 더 빠른 경우가 있기 때문이다.

 

☆ 필자의 코드 특성

: 벽을 부수는 방식을 boolean으로 체크하면 1회 한정으로만 가능한 코드가 된다.

이를 개선하여 게임 캐릭터의 능력치처럼 횟수를 원하는 만큼으로 지정할 수 있도록 작성했다.

즉, Node 객체의 Chance 필드를 boolean이 아닌 int형으로 둠으로써 각 객체(캐릭터)별로 횟수를 지정할 수 있고,

Chance가 0보다 큰 경우, 이전 값 -1로 변경함으로서  횟수 제한의 자유도를 높였다.

 

---

나의 코드

1. 2차원 배열을 이용한 방문 체크 방식 [실패]

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

public class no2206 {
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    private static String[][] map;
    private static boolean[][] visited;
    private static int[] hor = {-1, 1, 0, 0};
    private static int[] ver = {0, 0, -1, 1};
    private static int N, M;
    private static int min = 1000001;
    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");    
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = new String[N][M];
        visited = new boolean[N][M];

        for(int i=0 ; i<N ; i++) {
            String temp = br.readLine();
            for (int j=0 ; j<M ; j++) map[i][j] = String.valueOf(temp.charAt(j));
        }

        BFS();

        if(min == 1000001) System.out.println(-1);
        else System.out.println(min);
    }

    private static void BFS () {
        Deque<Node> dq = new ArrayDeque<>();
        dq.add(new Node(0, 0, 1, 1));
        visited[0][0] = true;

        while(!dq.isEmpty()) {
            Node now = dq.poll();
            int nowX = now.X;
            int nowY = now.Y;

            if(nowY == N-1 && nowX == M-1) {
                min = now.Step;
                break;
            }

            for(int i = 0 ; i<4 ; i++) {
                int nextX = nowX+hor[i];
                int nextY = nowY+ver[i];

                if(0<=nextY && nextY<N && 0<=nextX && nextX<M && !visited[nextY][nextX]) {

                    // 1일때
                    if(map[nextY][nextX].equals("1")) {
                        if(now.Chance==1) { // 벽을 부술때
                            dq.add(new Node(nextX, nextY, now.Step+1, 0));
                        } 
                    } 

                    // 0일때
                    else if(now.Chance==0) { // map에서 0일 경우 중, 벽 부술 찬스가 없는 경우
                        dq.add(new Node(nextX, nextY, now.Step+1, 0));
                    } else { // map에서 0일 경우 중, 벽 부술 찬스가 있는 경우
                        dq.add(new Node(nextX, nextY, now.Step+1, 1));
                    }

                    visited[nextY][nextX] = true;
                }               
            }
        }
    }

    private static class Node {
        private int X;
        private int Y;
        private int Step;
        private int Chance;

        public Node (int x, int y, int step, int chance) {
            this.X = x;
            this.Y = y;
            this.Step = step;
            this.Chance = chance;
        }
    }
}

 

2. 3차원 배열을 이용한 방문체크 방식 [성공]

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

public class no2206 {
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static int N, M;
    private static char[][] map;
    private static int[] ver = {0,0,-1,1};
    private static int[] hor = {-1,1,0,0};
    private static boolean[][][] visited = new boolean[N][M][2]; // 벽을 부수는 탐색과, 부수지 않는 탐색때문에 3차원의 크기가 2임

    private static class Node {
        private int Y;
        private int X;
        private int Step;
        private int Chance;

        public Node (int y, int x, int step, int chance) {
            this.Y = y;
            this.X = x;
            this.Step = step;
            this.Chance = chance;
        }
    }

    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = new char[N][M];
        for (int i=0 ; i<N ; i++) {
            String input = br.readLine();
            for (int j=0 ; j<M ; j++) {
                map[i][j] = input.charAt(j);
            }
        }

        int result = BFS();
        System.out.println(result);
    }

    private static int BFS() {
        Deque<Node> dq = new ArrayDeque<>();
        dq.add(new Node(0, 0, 1, 1));
        visited = new boolean[N][M][2];

        while (!dq.isEmpty()) {
            Node now = dq.poll();

            // 최초 도달지점은 곧 최소 스텝
            if(now.Y == N-1 && now.X == M-1) return now.Step;

            for(int i=0 ; i<4 ; i++) {
                int nextY = now.Y + ver[i];
                int nextX = now.X + hor[i];

                if(nextY<0 || N<=nextY || nextX<0 || M<=nextX) continue;

                // 벽이 아닐 경우
                if(map[nextY][nextX]=='0') {
                    // 벽을 부순적이 없는 경우 => 벽 부술 기회 유지
                    if(now.Chance > 0 && !visited[nextY][nextX][0]) {
                        dq.add(new Node(nextY, nextX, now.Step+1, now.Chance));
                        visited[nextY][nextX][0] = true;
                    }
                    // 벽을 부순적이 있는 경우 => 벽 부술 기회 없는 것 체크
                    else if (now.Chance == 0 && !visited[nextY][nextX][1]) {
                        dq.add(new Node(nextY, nextX, now.Step +1, now.Chance));
                        visited[nextY][nextX][1] = true;
                    }
                } 

                // 벽인 경우
                else if(map[nextY][nextX]=='1') {
                    // 벽을 부순적이 없는 경우 => 벽 부술 기회 - 1
                    if(now.Chance > 0) {
                        dq.add(new Node(nextY, nextX, now.Step + 1, now.Chance - 1));
                        visited[nextY][nextX][1] = true;
                    }
                    // 벽 부순적이 있는 경우 여기서 중지(아무런 조취 X)
                }
            }
        }
        
        return -1;
    }
}

---

레퍼런스 코드

 

 

참고 링크1 (3중 배열 방식 ) : https://kim6394.tistory.com/201

참고 링크2 : https://velog.io/@yanghl98/%EB%B0%B1%EC%A4%80-2206-%EB%B2%BD-%EB%B6%80%EC%88%98%EA%B3%A0-%EC%9D%B4%EB%8F%99%ED%95%98%EA%B8%B0-JAVA%EC%9E%90%EB%B0%94