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

2206 문제 링크

---

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

 

문제 설명

---

 

입출력

---

 

코드

---

import java.io.*;
import java.util.*;
 
public class Main {
    static int N, M;
    static int[][] arr;
    static boolean[][][] visit;
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {1, -1, 0, 0};
    public static void main(String[] args) throws IOException {
        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());
        arr = new int[N+1][M+1];
        dist = new int[N+1][M+1];
        visit = new boolean[N+1][M+1][2];
        for (int i = 1; i <= N; i++) {
            String line = br.readLine();
            for (int j = 1; j <= M; j++) {
                arr[i][j] = line.charAt(j-1) - '0';
            } 
        } 
        bw.write(String.valueOf(bfs()));
        bw.flush();
    }
    private static int bfs() {
        Queue<Node> queue = new LinkedList<>();
        visit[1][1][0] = true;
        visit[1][1][1] = true;
        queue.offer(new Node (1, 1, 1, 0));
        while(!queue.isEmpty()) {
            Node current = queue.poll();
            if (current.x == N && current.y == M) {
                return current.count;
            } 
            for (int i = 0; i < 4; i++) {
                int nx = current.x + dx[i];
                int ny = current.y + dy[i];
                if (nx > 0 && ny > 0 && nx <= N && ny <= M) {
                    if (arr[nx][ny] == 0) {
                        if (!visit[nx][ny][current.wall]) {
                            queue.offer(new Node(nx, ny, current.count+1, current.wall));
                            visit[nx][ny][current.wall] = true;
                        } 
                    } else {
                        if (current.wall == 0 && !visit[nx][ny][1]) {
                            queue.offer(new Node(nx, ny, current.count+1, 1));
                            visit[nx][ny][1] = true;
                        }
                    }
                } 
            } 
        }
        return -1;
    }
    private static class Node {
        private int x;
        private int y;
        private int count;
        private int wall;
        
        public Node(int x, int y, int count, int wall) {
            this.x = x;
            this.y = y;
            this.count = count;
            this.wall = wall;
        }
    }
}

 

알고리즘 설명

---

벽을 한 개까지는 부술 수 있다는 그래프의 모든 원소에 적용가능하도록 정리해보자면, 첫 번째 출발 원소를 제외한, 모든 원소는 지나온 길에 대해 벽을 부순 기록이 0이라면, 벽을 한 번 부술 수 있고, 벽을 부순 기록이 1이라면, 이 후 길찾기에 대해서는 벽을 부술 수 없다는 말입니다. 이동한 좌표에 대해 벽을 부쉈는지 여부에 따라 같은 좌표라도 다른 상태인데, 2차원 visit배열로는 어떠한 좌표에 대해 벽을 부수고 도착했는지, 아닌지를 알 수 없기때문에 visit배열을 3차원으로 만들어, 벽을 부쉈는지 기록할 수 있도록 합니다. 한 번의 이동에 기록할 변수가 많기 때문에 좌표x, 좌표y, 이동횟수, 벽을 부쉈는지 여부 총 네 가지를 기록할 Node객체를 생성해 벽을 부수지 않은 상태(0)와 부순 상태(1)를 구분해서 탐색하고, (N,M)에 도착하면 최소 이동 횟수를 반환합니다. visit배열에 벽을 부쉈는지의 여부를 기록하는 것을 제외하면 bfs와 동일한 방식입니다. 탐색 알고리즘은 익숙해질만 하면, 꼭 어려운 문제들이 등장하는 것 같습니다.

 

코드 해석

---

arr배열을 생성하고 한줄에 입력된 String을 각 Character로 나누어 해당 입력을 유지하도록 아스키코드 0값인 48을 빼준채로 arr에 차례대로 입력합니다. 좌표값과 이동횟수(count), 벽 부심 여부(wall)를 저장할 Node객체를 선언하고 bfs()함수에서 생성한 큐에 시작좌표와 그 정보인 (1, 1, 1, 0)을 집어넣습니다. 이후, 빠져나온 큐의 값을 기준으로 dx, dy값에 따라 좌표이동을 실시하고, nx는 1부터 N까지, ny는 1부터 M까지 이동이 가능하도록 조건을 생성하고 벽이 아닌경우와, 벽을 만났을 경우로 나누어 BFS탐색을 진행합니다. nx, ny값이 N, M값과 동일하다면 현재 count값을 반환하고, 종료합니다. while문이 끝났는데도 nx, ny가 N,M에 도착하지못했다면 -1을 반환합니다.