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

❓ 문제 - 백준 벽 부수고 이동하기 2206번 - JAVA 풀이법

 

출처 

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

2206번: 벽 부수고 이동하기

 

 

 

📝 문제해결법

1. 이 문제는 BFS 알고리즘을 사용해서 풀었다.

• N, M의 값이 1000으로 큰 값이기 때문에 시간을 고려해서 풀어야 한다. -> BFS
• 벽은 한 번 부술 수 있으므로 벽을 부쉈을 때 방문체크 배열, 벽을 안 부쉈을 때 방문체크 배열을 따로 만들어야 한다.
• 해당 위치에 벽을 부순 상태로 이미 방문했거나, 아직 벽을 부수지 않은 상태로 이미 방문 했지만 마지막에 벽에 막혀 방문하지 못 했을때, 다른 꼬불꼬불 길을 지나면서 해당 벽을 부수고 도착지에 올 수 있는 애가 이미 방문 처리 되었어서 그곳을 지날 수 없어 목적지에 도달 못한다고 판단할 수 있기 때문이다.
• BFS 내에서는 4방향으로 탐색하면서, 아직 벽 부순 여부에 맞는 방문배열에 방문 처리가 되지 않았으면서, 이동할 곳이 지나갈 수 있으면 방문 처리 후 이동거리를 1 증가시킨 Node객체를 큐에 넣는다.
• 그리고 이동할 곳이 벽이지만, 아직 벽을 부순 적이 없을 때 해당 벽을 부쉈을 때 방문처리 할곳에 방문처리하고, 벽을 부쉈다고 상태 변경하고 이동거리를 1 증가시킨 Node 객체를 큐에 넣는다.

2. 문제를 풀면서 느낀점

• 파이썬으로 풀었는데, 자바로 다시 도전할 때 나름 만만하게 생각하다가 계속 메모리 초과 났다...
• 나는 공간을 많이 잡아먹어서 메모리 초과가 나는 줄 알았는데 히든 테스트 케이스에서 방문처리 관련 잘못 구현하여 while문을 만약 빠져 나가지 못 했고 이게 메모리 초과가 났다..
• 무한반복문에 빠져도 메모리초과와 같은 메시지를 받을 수 있다는 것을 명심하자...
• 그리고 방문배열은 단순히 모든 경우의 수에서 방문 처리를 통해 계산하는 경우를 줄이기 위해 사용하므로, 이 문제에서 주어진 벽을 부순 상태에서 이동, 벽을 부수지 않은 상태에서 이동의 경우을 모두 살필 수 있게 방문 배열을 만들어야 하구나..!!!!!!!!!!!!!!!

 

💻 소스코드

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

public class Main_2206 {
    static int map[][];  // 통로 정보 입력 받을 배열
    static int visited[][][]; // visited[][][0] -> 아직 벽 부수지 않고 방문체크, visited[][][1] -> 벽 부순 후 방문 체크
    static int min_dis;
    public static class Node {
        int x;
        int y;
        int use;
        int dis;
        public Node(int x, int y, int use, int dis){
            this.x = x;
            this.y = y;
            this.use = use;
            this.dis = dis;

        }
    }
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static int n, m;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] str = br.readLine().split(" ");
        n = Integer.parseInt(str[0]);
        m = Integer.parseInt(str[1]);

        map = new int[n][m];
        visited = new int[n][m][2];
        // 지나가는 통로 정보 입력 받기
        for(int i=0;i<n;i++){
            String data = br.readLine();
            for(int j=0;j<m;j++){
                map[i][j] = data.charAt(j) -'0';
            }
        }
        min_dis = Integer.MAX_VALUE;
        // bfs 돌아서 움직이면서 map[n-1][m-1] 까지 가는 최소값 구하기
        bfs();
        // 만약 bfs 다 돌았는데 n-1, m-1 도달하지 못하면 min_dis 는 초기 주어진 값이므로 -1 출력하고
        // bfs 돌았는데 최소값 구하면 해당 값 출력
        if(min_dis == Integer.MAX_VALUE){
            System.out.println("-1");
        } else{
            System.out.println(min_dis);
        }



    }

    public static void bfs() {
        Queue<Node> q = new LinkedList<>();
        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};
        // Node 객체에 행, 열 위치정보, 벽 부쉈는지 여부(0, 1), 이동 거리
        // 이동거리가 1인 이유는 문제에서 시작하는 칸과 끝나는 칸도 포함해서 이동거리를 센다고 조건 반영
        q.add(new Node(0, 0, 0, 1));
        // 0, 0은 아직 벽을 부수지 않은 상태(0)에서 방문처리
        visited[0][0][0] = 1;

        // queue가 빌 때까지 완전탐색
        while (!q.isEmpty()) {
            Node node = q.poll();
            // 만약 다 돌고 난 후 도착지이면 이때까지 이동할 때까지 걸린 거리를 최소 이동 거리랑 비교해서 최솟값 갱신
            if (node.x == n - 1 && node.y == m - 1) {
                min_dis = Math.min(min_dis, node.dis);
            }
            // 4방향 탐색
            for (int k = 0; k < 4; k++) {
                int nx = node.x + dx[k];
                int ny = node.y + dy[k];
                // 범위 벗어나지 않게 체크
                if (0 <= nx && nx < n && 0 <= ny && ny < m) {
                    // 만약 방문했다면(이미 처리) 이곳은 탐색하지 않음
                  if(visited[nx][ny][node.use] != 0){
                      continue;
                  }

                  if (map[nx][ny] == 0){
                      // 이동할 곳이 이동할 수 있는 곳이면, 방문 처리 후 q에 이동거리 1증가시킨 node 객체 생성해서 큐에 추가
                      visited[nx][ny][node.use] = 1;
                      q.add(new Node(nx, ny, node.use, node.dis+1));
                  } else if(map[nx][ny] == 1 && node.use == 0){
                      // 만약 한번도 부순 적 없는 상태에서 벽을 만나면 한 번 벽을 부순 후 지나갈 수 있으므로
                      // 벽을 부순상태로 변경하고, 방문처리 후 큐에 추가
                      visited[nx][ny][1] = 1;
                      q.add(new Node(nx, ny, 1, node.dis+1));
                  }
                }

            }
        }
    }
}