[백준] 2206번 : 벽 부수고 이동하기 (java)

2206번: 벽 부수고 이동하기 (acmicpc.net)

2206번: 벽 부수고 이동하기

어떻게 생각하고 문제를 풀었는가?

(1,1)부터 (N,M)까지의 최단 경로를 구하기 위해서는 BFS를 사용하여 문제를 해결할 수 있을 것이라고 생각하였습니다.

문제에서 단 한번 벽을 부술 수 있다는 것을 고려해야 하는데, 이를 해결하기 위해서 벽을 부순 상태에서의 최단거리와 벽을 부수지 않은 상태에서의 최단거리를 별도로 계산하여 해결하고자 하였습니다.

코드

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
        int N = Integer.parseInt(tokenizer.nextToken());
        int M = Integer.parseInt(tokenizer.nextToken());
        String[] board = new String[N];
        for(int i=0; i<N; i++){
            board[i] = reader.readLine();
        }
        reader.close();
        int[][][] dist = new int[N][M][2];
        Queue<Player> queue = new LinkedList<>();
        queue.add(new Player(0,0, 0));
        dist[0][0][0]=1;
        int min = -1;
        while(!queue.isEmpty()){
            Player current = queue.poll();
            int currentRow = current.row;
            int currentColumn = current.column;
            int destroyed = current.destroyed;
            if(currentRow==N-1 && currentColumn==M-1){
                min = dist[currentRow][currentColumn][destroyed];
                break;
            }

            if(currentRow>0){
                if(board[currentRow-1].charAt(currentColumn)=='0' && dist[currentRow-1][currentColumn][destroyed] == 0){
                    queue.add(new Player(currentRow-1, currentColumn, destroyed));
                    dist[currentRow-1][currentColumn][destroyed] = dist[currentRow][currentColumn][destroyed]+1;
                }else if(board[currentRow-1].charAt(currentColumn)!='0' && destroyed==0 && dist[currentRow-1][currentColumn][1] == 0){
                    queue.add(new Player(currentRow-1, currentColumn,1));
                    dist[currentRow-1][currentColumn][1] = dist[currentRow][currentColumn][destroyed]+1;
                }
            }

            if(currentColumn>0){
                if(board[currentRow].charAt(currentColumn-1)=='0' && dist[currentRow][currentColumn-1][destroyed] == 0){
                    queue.add(new Player(currentRow, currentColumn-1, destroyed));
                    dist[currentRow][currentColumn-1][destroyed] = dist[currentRow][currentColumn][destroyed]+1;
                }else if(board[currentRow].charAt(currentColumn-1)!='0' && destroyed==0 && dist[currentRow][currentColumn-1][1]==0){
                    queue.add(new Player(currentRow, currentColumn-1,1));
                    dist[currentRow][currentColumn-1][1] = dist[currentRow][currentColumn][destroyed]+1;
                }
            }

            if(currentColumn+1<M){
                if(board[currentRow].charAt(currentColumn+1)=='0' && dist[currentRow][currentColumn+1][destroyed]==0){
                    queue.add(new Player(currentRow, currentColumn+1, destroyed));
                    dist[currentRow][currentColumn+1][destroyed] = dist[currentRow][currentColumn][destroyed]+1;
                }else if(board[currentRow].charAt(currentColumn+1)!='0' && destroyed==0 && dist[currentRow][currentColumn+1][1]==0){
                    queue.add(new Player(currentRow, currentColumn+1,1));
                    dist[currentRow][currentColumn+1][1] = dist[currentRow][currentColumn][destroyed]+1;
                }
            }

            if(currentRow+1<N){
                if(board[currentRow+1].charAt(currentColumn)=='0' && dist[currentRow+1][currentColumn][destroyed]==0){
                    queue.add(new Player(currentRow+1, currentColumn, destroyed));
                    dist[currentRow+1][currentColumn][destroyed] = dist[currentRow][currentColumn][destroyed]+1;
                }else if(board[currentRow+1].charAt(currentColumn)!='0' && destroyed==0 && dist[currentRow+1][currentColumn][1]==0){
                    queue.add(new Player(currentRow+1, currentColumn,1));
                    dist[currentRow+1][currentColumn][1] = dist[currentRow][currentColumn][destroyed]+1;
                }
            }
        }
        System.out.println(min);
    }

    static class Player{
        int row;
        int column;
        int destroyed;
        Player(int row, int column, int destroyed){
            this.row = row;
            this.column = column;
            this.destroyed = destroyed;
        }
    }

}

Queue를 사용하여 BFS를 구현하였습니다.

상/하/좌/우 네방향으로 이동할 수 있는지 체크하고, 벽이 있고 부술 수 있다면 벽을 부순 상태의 최단거리를 계산합니다.

BFS이므로 먼저 도착한 결과는 최단거리를 갖습니다. 변수 min의 값을 갱신하고 갱신되지 않았을 경우 초기화 값인 -1을 결과로 출력합니다.