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

1. 문제

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

2206번: 벽 부수고 이동하기

2. 풀이 Point

<Error Point>

• (1) 벽을 만날 때마다 벽을 부수고 bfs 돌리는건 시간 초과가 난다.
  • 벽을 탐색한다면 NM의 시간이 걸리고 이에 대하여 각각 bfs로 탐색하므로 (NM)^2의 시간이 걸린다.
• (2) 벽을 부쉈는지 안 부쉈는지 객체 안에 flag 변수를 두거나 visited 배열을 boolean으로 두는 경우는 탐색을 할 수가 없거나 잘못된 값을 반환한다.

• (3) visited를 int 타입의 2차원 배열로 만들자
  • (3-1) 전부 0으로 초기화
    1. 전부 0으로 초기화를 해주면 bfs 탐색 조건문에서 현재 탐색하려고 하는 객체의 visitedCnt보다 visited 배열의 값이 작아야 하는데 (visited[xf][yf] < poll.visitedCnt), (ex : visited 값 : 0, 1번 벽을 부수고 온 경우 : 1), 이러면 위 사진과 같이 벽이 없는 부분을 따라온 경우는 초록색 부분으로 갈 수 없다. (ex : 1번 벽을 부수고 온 경우 : 1, 0만을 탐색해온 경우 : 0)

<풀이 Point>

• visited 배열을 int형으로 선언한다!!(boolean으로 처리시 위와 같은 사례가 발생할 수 있음)
• 입력을 받을 때 visited 배열을 2로 초기화( 어차피 벽은 1번 밖에 못 부시므로 탐색하면서 갱신하는 visited의 값은 0, 1만을 가진다. 따라서 나올 수 없는 값 중 최대 값인 2로 초기화 시켜준다.)
• 그 후 bfs를 돌면서 벽이 나오는 경우 or 벽이 아닌 경우의 분기를 설정해준다.
  • 벽이 나오는 경우
    • 벽이 나오는 경우는 현재 객체의 visitedCnt 값을 봐줘야 한다.
      1. 현재 객체의 visitedCnt 값이 0인 경우
         • 이 경우는 지금까지 벽을 부순적이 한번도 없으므로 벽을 부수고 갈 수 있는 경우가 있다. 따라서 visitedCnt 값을 하나 증가시켜 준 후 큐에 넣는다.
      2. 현재 객체의 visitedCnt 값이 0이 아닌 경우
         • 이 경우는 벽을 부순 전적이 있는 것이다. 벽은 한 번밖에 못 부수므로 이는 탐색할 수 없다.
  • 벽이 아닌 경우
    • 벽이 아닌 경우는 move를 하나 증가시켜준 후 다시 큐에 넣으면 된다.
• 마지막으로 끝점에 도달했다면 그때까지 간 결과 중 최소값을 출력하고, 만약 결과값이 처음에 설정해둔 값 그대로라면 이는 목표 지점까지 가지 못한 경우이므로 “-1”을 출력한다.
  
  
  

3. 소스 코드

// 시간 초과 코드 : (1)번 코드
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

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

    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};
    static int result = Integer.MAX_VALUE;
    static boolean flag = false; // 벽을 부쉇다는 플래그 (true : 부쉇음, false : 안 부쉇음)

    static class Point {
        int x;
        int y;
        int move;

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

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = new int[N][M];
        visited = new boolean[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) - '0';
            }
        }
        beforeBreakWallBFS(0, 0, 1);

        if (result == Integer.MAX_VALUE) {
            bw.write("-1");
        } else {
            bw.write(Integer.toString(result));
        }
        bw.flush();
        bw.close();
        br.close();
    }

    private static void beforeBreakWallBFS(int x, int y, int move) {
        Queue<Point> q = new LinkedList<>();
        q.add(new Point(x, y, move));
        visited[x][y] = true;

        while (!q.isEmpty()) {
            Point poll = q.poll();
            visited[poll.x][poll.y] = true;

            if (poll.x == N - 1 && poll.y == M - 1){
                result = Math.min(result, poll.move);
                return;
            }

            for (int i = 0; i < 4; i++) {
                int xf = poll.x + dx[i];
                int yf = poll.y + dy[i];

                if (xf >= 0 && xf < N && yf >= 0 && yf < M && !visited[xf][yf]) {
                    visited[xf][yf] = true;

                    // 벽을 만났는데 아직 안뚫었음
                    if (map[xf][yf] == 1 && !flag) {
                        int[][] copyMap = new int[N][M];
                        boolean[][] copyVisited = new boolean[N][M];

                        for (int j = 0; j < map.length; j++) {
                            copyMap[j] = map[j].clone();
                        }

                        for (int j = 0; j < visited.length; j++) {
                            copyVisited[j] = visited[j].clone();
                        }

                        Queue<Point> copyQ = new LinkedList<>(q);

                        copyMap[xf][yf] = 0;
                        copyVisited[xf][yf] = true;
                        copyQ.add(new Point(xf, yf, poll.move + 1));

                        flag = true;
                        afterBreakWallBFS(copyMap, copyQ, copyVisited);
                        flag = false;
                    } else {
                        q.add(new Point(xf, yf, poll.move + 1));
                    }
                }
            }
        }
    }

    private static void afterBreakWallBFS(int[][] copyMap, Queue<Point> copyQ, boolean[][] copyVisited) {
        while (!copyQ.isEmpty()) {
            Point poll = copyQ.poll();
            copyVisited[poll.x][poll.y] = true;

            if (poll.x == N - 1 && poll.y == M - 1){
                result = Math.min(result, poll.move);
                return;
            }

            for (int i = 0; i < 4; i++) {
                int xf = poll.x + dx[i];
                int yf = poll.y + dy[i];

                if (xf >= 0 && xf < N && yf >= 0 && yf < M && !copyVisited[xf][yf] && copyMap[xf][yf] != 1) {
                    copyVisited[xf][yf] = true;
                    copyQ.add(new Point(xf, yf, poll.move + 1));
                }
            }
        }
    }
}

<정답 코드>

// 정답 코드
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

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

    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};
    static int result = Integer.MAX_VALUE;

    static class Point {
        int x;
        int y;
        int move;
        int visitedCnt; // 벽을 부순 횟수 (벽을 부쉈는지 아닌지 boolean으로는 할 수 없음)

        public Point(int x, int y, int move, int visitedCnt) {
            this.x = x;
            this.y = y;
            this.move = move;
            this.visitedCnt = visitedCnt;
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = new int[N][M];
        visited = new int[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) - '0';
                visited[i][j] = 2; // visited 카운트를 2로 초기화, 어차피 벽은 1번 밖에 못 부시므로 1 이상의 값이 나올 수 없다.
            }
        }
        breakWallBFS(0, 0, 1, 0);

        if (result == Integer.MAX_VALUE) {
            bw.write("-1");
        } else {
            bw.write(Integer.toString(result));
        }
        bw.flush();
        bw.close();
        br.close();
    }

    private static void breakWallBFS(int x, int y, int move, int visitedCnt) {
        Queue<Point> q = new LinkedList<>();
        q.add(new Point(x, y, move, visitedCnt));
        visited[x][y] = 0;

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

            if (poll.x == N - 1 && poll.y == M - 1) {
                result = Math.min(result, poll.move);
                break;
            }

            for (int i = 0; i < 4; i++) {
                int xf = poll.x + dx[i];
                int yf = poll.y + dy[i];

                if (xf >= 0 && xf < N && yf >= 0 && yf < M && (visited[xf][yf] > poll.visitedCnt)) {
                    // 벽을 만났음
                    if (map[xf][yf] == 1) {
                        if (poll.visitedCnt == 0) { // 지금 큐에서 꺼낸 객체(탐색하고 있는 객체)가 한번도 벽을 안 부쉈다면
                            visited[xf][yf] = poll.visitedCnt + 1;
                            q.add(new Point(xf, yf, poll.move + 1, poll.visitedCnt + 1));
                        }

                       // 지금 큐에서 꺼낸 객체(탐색하고 있는 객체)가 한번이라도 벽을 부쉈다면 벽을 또 부술 수 없으므로 기각
                    }

                    // 벽이 아닌 경우 : 그대로 탐색 진행
                    else if (map[xf][yf] == 0) {
                        visited[xf][yf] = poll.visitedCnt;
                        q.add(new Point(xf, yf, poll.move + 1, poll.visitedCnt));
                    }
                }
            }
        }
    }
}

 

4. 배운점

1. 알고리즘의 시간초과를 잘 따져서 문제를 해결하자.(bfs : (1) 인접 행렬 : O(N^2), (2) 인접리스트 : (V + E)
2. 방문 배열은 꼭 boolean일 필요 없다.(정형화된 생각을 버리자) 방문했던 곳에 또 방문할 수가 있다.
   
   
   

5. 점수

75/100