[백준/JAVA] 2206번: 벽 부수고 이동하기

🔺 문제

2206번: 벽 부수고 이동하기

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] dx = {0,0,-1,1};
    static int[] dy = {1,-1,0,0};
    
    static int N, M;
    static int[][] map, dist;     // 미로 배열, 거리 측정 배열
    static boolean[][][] visited; // 🔔 벽을 부순 여부에 따라 방문 여부 기록 (부서진 여부, x, y)
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        
        map = new int[N][M];
        dist = new int[N][M];
        
        for(int i = 0 ; i < N ; i++) {
            String str = br.readLine();
            for(int j = 0 ; j < M ; j++) {
                map[i][j] = str.charAt(j) - '0';
            }
        }
        
        if(N - 1 == 0 && M - 1 == 0) {
            System.out.println(1);
            System.exit(0);
        }
        
        visited = new boolean[2][N + 1][M + 1];
        System.out.println(bfs(0, 0, 0));
    }
    
    private static int bfs(int breakCnt, int a, int b) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[] {a, b, 0}); // x좌표, y좌표, crash 여부
        
        visited[breakCnt][a][b] = true;
        
        while(!queue.isEmpty()) {
            int[] now = queue.poll();
            
            for(int d = 0 ; d < 4 ; d++) {
                int x = now[0] + dx[d];
                int y = now[1] + dy[d];
                
                if(x < 0 || y < 0 || x >= N || y >= M)    continue;
 
                if(map[x][y] == 1) {    // [벽인 경우]
                    if(now[2] == 0 && !visited[1][x][y]) {  // 부순 적 없고, 방문한 적 없을 때
                        visited[now[2]][x][y] = true;
                        dist[x][y] = dist[now[0]][now[1]] + 1;
                        queue.offer(new int[] {x, y, 1}); // 1: 벽 부순 처리
                    }    
                }
                else {  // [벽이 아닌 경우]
                    if(!visited[now[2]][x][y]) {
                        visited[now[2]][x][y] = true;
                        dist[x][y] = dist[now[0]][now[1]] + 1;
                        queue.offer(new int[] {x, y, now[2]}); // now[2] : 지금 값 그대로
                    }
                }
                
                // 🔔 도착 지점 만나면 종료
                if(x == N - 1 && y == M - 1) {
                    return dist[x][y] + 1;
                }
            }
            
        } 
 
        return -1;
    }
}

✅ 해결 아이디어
✔ BFS
- visited 배열을 3중으로 만들어 [벽을 부수고 / 부수지 않고 탐색하는 경우] 따로 처리
  ⇨ visited[0][N][M] : 벽을 한 번도 안 부순 애들이 탐색한 경우
  ⇨ visited[1][N][M] : 벽을 한 번 부수고 탐색한 경우

 

🧩 필요 자료구조

•  int[] dx/dy      : 상하좌우 이동용

•  int[][] map      : 미로 배열

•  int[][] dist    : 거리 저장 2차원 배열

•  boolean[][][]  : 벽을 부순 여부에 따라 방문 여부 기록 (부서진 여부, x, y)

•  Queue<int[]>     : BFS 수행용 큐  (x좌표, y좌표, crash 여부)

 

 

💥 유의사항

 BFS 탐색 조건

▸벽인 경우

  - 한 번도 벽을 부신 적 없고 방문한 적 없으면 > 부수고 + 방문 처리하고 + 큐에 넣기

 

▸벽이 아닌 경우

  -  방문 처리하고 + 큐에 넣기

 

---

🔺 다른 풀이들

- 클래스에 (x,y, 갯수, 부서진 여부) 이렇게 4개 인자를 갖고 푸셨다.

[백준] 2206 : 벽 부수고 이동하기 (JAVA/자바)

---

💬 느낀 점

벽을 부수는 경우에 대한 BFS 방문처리는

visited배열을 3중 배열로 만들어 각각 처리하자!

 

boolean 타입 변수로 벽을 부쉈는지 여부 판별하고, 최단거리 구하려고 했는데

이렇게 되면 '벽을 부수지 않고 이동했을 때'와 '벽을 부수고 이동했을 때'의 이동경로가 겹쳐

최단거리라도 더 이상 진행하지 못 한다고 한다. (참고)

 

1회독	2회독	3회독	4회독	5회독
V	231219	240407

 

 

(+2회독 12.19)

코드 확인하기

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] dx = {0, 0, -1, 1,};
    static int[] dy = {1, -1, 0,0,};
    
    static int N, M, breakCnt;
    static int[][] map, dist;
    static boolean[][][] visited;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        
        map = new int[N][M];
        dist = new int[N][M];
        
        for(int i = 0 ; i < N ; i++) {
            String str = br.readLine();
            for(int j = 0 ; j < M ; j++) {
                map[i][j] = str.charAt(j) - '0';
            }
        }
        
        if(N - 1 == 0 && M - 1 == 0) {
            System.out.println(1);
            return;
        }
        
        visited = new boolean[2][N + 1][M + 1];
        System.out.println(bfs(0, 0, 0));
    }
    
    private static int bfs(int breakCnt, int x, int y) {
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[] {x, y, 0});
        
        visited[breakCnt][x][y] = true;
        
        while(!q.isEmpty()) {
            int[] now = q.poll();
            
            for(int d = 0 ; d < 4 ; d++) {
                int nx = now[0] + dx[d];
                int ny = now[1] + dy[d];
                
                if(nx < 0 || ny < 0 || nx >= N || ny >= M)  continue;
                
                if(map[nx][ny] == 1) {
                    if(now[2] == 0 && !visited[1][nx][ny]) {
                        visited[now[2]][nx][ny] = true;
                        dist[nx][ny] = dist[now[0]][now[1]] + 1;
                        q.offer(new int[] {nx, ny, 1});
                    }
                }
                else {
                    if(!visited[now[2]][nx][ny]) {
                        visited[now[2]][nx][ny] = true;
                        dist[nx][ny] = dist[now[0]][now[1]] + 1;
                        q.offer(new int[] {nx, ny, now[2]});
                    }
                }
                
                if(nx == N - 1 && ny == M - 1) {
                    return dist[nx][ny] + 1;
                }
            }
        }
        
        return -1;
    }
}
 

 

 

 

 

 

(+ 240407 3회독 : 88140KB, 672ms) ✅

코드 확인하기

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    
    static int N, M;
    static int[][] map;
    static boolean[][][] visited;   // 부서짐 여부 (1: 부서짐), 행, 열
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        
        if(N == 1 && M == 1) {  // 이거 빠뜨리면 97%에서 틀림
            System.out.println(1);
            return;
        }
        
        map = new int[N][M];
        visited = new boolean[2][N][M];
        
        for(int i = 0 ; i < N ; i++) {
            String str = br.readLine();
            for(int j = 0 ; j < M ; j++) {
                map[i][j] = str.charAt(j) - '0';
            }
        }
        
        System.out.println(bfs());
    }
    
    private static int bfs() {
        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[] {0,0,0});  // 행, 열, 부숴짐 여부 (1: 부서짐)
        
        visited[0][0][0] = true;
        
        while(!q.isEmpty()) {
            int[] now = q.poll();
            
            int x = now[0];
            int y = now[1];
            int crashed = now[2];
            
            for(int d = 0 ; d < 4 ; d++) {
                int nx = x + dx[d];
                int ny = y + dy[d];
                
                if(nx < 0 || nx >= N || ny < 0 || ny >= M)  continue;
                
                if(map[nx][ny] == 1) {  // 벽인 경우
                    if(crashed == 0 && !visited[1][nx][ny]) {  // 부서진 적, 방문한 적 없는 벽인 경우
                        visited[crashed][nx][ny] = true;
                        map[nx][ny] = map[x][y] + 1;
                        q.add(new int[] {nx, ny, 1}); // 1: 벽 부숨
                    }
                }
                else {  // 빈 칸인 경우
                    if(!visited[crashed][nx][ny]) {
                        visited[crashed][nx][ny] = true;
                        map[nx][ny] = map[x][y] + 1;
                        q.add(new int[] {nx, ny, crashed});  // 지금 값 그대로
                    }
                }
                
                // 도착 지점 (N-1, M-1) 도착하면 종료
                if(nx == N -1 && ny == M-1) {
                    return map[nx][ny] + 1;
                }
            }
        }
        
        return -1;  // 도착 지점 못 도달하면 -1
    }
}
 

 

 

---

(참고)

백준 2206번 : 벽 부수고 이동하기 (JAVA) 문제 풀이

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