[백준] code.plus(BFS 알고리즘,JAVA)16933번, 벽 부수고 이동하기 3

문제 링크

16933번: 벽 부수고 이동하기 3

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

 

접근 방법

그래프 알고리즘이란?

각 정점과 연결하는 선분의 정보를 가지고 BFS(너비 우선 탐색), DFS(깊이 우선 탐색) .... 등을 이용하여 정점에서 다른 정점으로 가는 최소값, 최대값 등의 문제에서 출력하라는 결과를 구하는 알고리즘입니다.

 

BFS?

BFS(너비 우선 탐색)은 아래 그림처럼 시작 노드에 인접한 노드를 모두 탐색한 후 인접한 노드를 기준으로 다시 인접한 노드를 찾아내는 것을 반복하여 탐색합니다.

시작 노드 탐색이 끝나면 인접했던 노드를 시작 노드로 생각하고 다시 탐색합니다.

출처: https://ko.wikipedia.org/wiki/%EB%84%88%EB%B9%84_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

더 자세한 내용은 아래 링크에 들어가서 확인해주시면 감사하겠습니다.

너비 우선 탐색 - 위키백과, 우리 모두의 백과사전

 

이 문제에 핵심은

1. 맵에서 이동할 수 있는 구간 0, 벽이 있는 구간 1로 주어집니다.

2. 벽을 부술 수 K번 이하로 부술 수 있습니다.

3. 낮에만 벽을 부술 수 있으며 제 자리에서 머무를 수 있습니다.

4. 벽을 부수거나 부수지 않는 모든 경우의 수 중 최단 거리를 결과로 출력한다.

 

벽을 K번 이하로 부술 수 있으므로 BFS탐색에 방문 확인에 대해서 벽을 몇 번 부수었을 때 방문했는지까지 확인합니다.

 

방문 확인 배열을 3차원으로 구성하였습니다.visited[N][M][K+1]

 

N = 세로

 

M = 가로

 

K = 벽을 부수는 최대 횟수

 

벽을 부순 횟수가 K번 이하일 때 벽을 인접한 경우

 

낮 : 바로 부수고 이동한다.

 

밤 : 한 번 머물렀다가 낮이 되었을 때 부수고 이동한다.

 

visited[1][4][1] : 벽을 1번 부수고 (4, 1)의 값에 도착하였을 때 방문했는지 확인

 

 

해당 방문 확인을 이용해서 BFS 탐색으로 진행해서 가장 먼저 도착점에 도달한 이동횟수는 최단 거리가 되지 않습니다.

 

밤에는 머무르는 경우가 있기 때문에 낮에 이동할 때 더 많은 거리를 이동했음에도 먼저 도착할 수 있기 때문입니다.

 

저는 이러한 경우를 없애기 위해서 PriorityQueue<>()를 사용하는 다익스트라 알고리즘으로 BFS탐색을 구현하였습니다.

데이크스트라 알고리즘 - 위키백과, 우리 모두의 백과사전

 

예제입력 4.

 

K = 2

0(출발)	1	0	0
1	1	1	0
1	0	0	0
0	0	0	0
0	1	1	1
0	0	0	0(도착)

 

출발지점부터 BFS탐색을 통해 진행합니다.

현재 상황 : 낮

현재 벽을 부순 횟수 : 0

0(출발)	1	0	0
1	1	1	0
1	0	0	0
0	0	0	0
0	1	1	1
0	0	0	0(도착)

이전에 벽을 부순 횟수가 0이며 낮이기 때문에 주변에 있는 벽을 부수고 이동할 수 있습니다.

 

(0, 1)을 탐색해보도록 하겠습니다.

현재 상황 : 밤

현재 벽을 부순 횟수 : 1

0(출발)	1	0	0
1	1	1	0
1	0	0	0
0	0	0	0
0	1	1	1
0	0	0	0(도착)

 

(0, 1)에서는 벽을 부순 횟수가 1이지만 현재 밤이기 때문에 0칸을 이동하거나 제자리에 머무를 수 있습니다.

그래서 (0, 1)에 머무르거나  (0, 2)을 탐색이 가능합니다.

 

BFS 탐색 중 ........

현재 상황 : 밤

현재 벽을 부순 횟수 : 1

0(출발)	1	0	0
1	1	1	0
1	0	0	0
0	0	0	0
0	1	1	1
0	0	0	0(도착)

가장 먼저 도착했을 때 거리 : 9

 

결과로 9를 출력합니다.

 

※PriorityQueue를 사용하지 않는 BFS탐색을 진행했을 때 가장 먼저 도착한 경우의 이동 거리는 10이 나옵니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer을 이용하여 N,M,K을 저장하였습니다.
• 시작지점에서 벽을 K번 이하로 부수며 다익스트라 BFS탐색하여 최단 거리를 구하는 bfs함수를 실행하였습니다.
• 최단 거리를 BufferedWriter에 저장합니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• bfs함수는 시작 지점에서 다익스트라 BFS 탐색을 진행합니다.
• bfs함수는 목적지에 도착하지 못하면 -1, 도착시 최단 거리를 반환한다.
• bfs함수는 낮에 벽을 만나면 거리 +1, 밤에 벽을 만나면 거리 + 2를 진행합니다.

※밤에는 벽을 부수고 이동하려면 낮이 될 때까지 해당 칸에 기다려야 하기 때문에 +2를 진행합니다.

 

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

public class Main {
	//다익스트라 BFS탐색에 우선순위 큐에 사용될 클래스
    static class position implements Comparable<position>{
        int x,y,count,wallBreak;
        boolean time;
        public position(int x, int y, int count, int wallBreak, boolean time) {
            this.x = x;
            this.y = y;
            this.count = count;
            this.wallBreak = wallBreak;
            this.time = time;
        }
        //이동 거리 오름차순으로 정렬되도록 Comparable 설정
        @Override
        public int compareTo( position o) {
            if(this.count > o.count)
                return 1;
            else
                return -1;
        }
    }
    static int N,M,K;
    static int[][] map;		//지도 관련 정보 배열
    static int[] dx = {0, 0, -1, 1};	//상하좌우 x값 변경값
    static int[] dy = {-1, 1, 0, 0};	//상하좌우 y값 변경값
    static public void  main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferdWriter
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        map = 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] = Character.getNumericValue(str.charAt(j));
            }
        }
        int result = bfs();		//다익스트라 BFS탐색으로 최단 거리 구하기
        bw.write(result + "\n");	//최단 거리 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //다익스트라 BFS탐색으로 최단 거리 구하는 함수
    static int bfs(){
    	//우선순위 큐 초기화
        PriorityQueue<position> queue = new PriorityQueue<>();
        boolean visited[][][] = new boolean[N][M][K+1];
        visited[0][0][0] = true;		//출발 지점 방문 확인
        queue.add(new position(0,0,1,0,true));	//출발 지점 우선순위 큐에 저장
        while(!queue.isEmpty()){
            position cur = queue.poll();
            int x = cur.x;
            int y = cur.y;
            int count = cur.count;
            int wallBreak = cur.wallBreak;
            boolean time = cur.time;
            if(x==M-1 && y==N-1)		//도착 지점에 도달시 거리 반환
                return count;
            for(int i=0;i<4;i++){
                int tempX = x + dx[i];
                int tempY = y + dy[i];
                if(tempX>=0 && tempY>=0 && tempX<M && tempY<N){
                	//인접한 이동할 수 있는 칸을 만났을 때
                    if(!visited[tempY][tempX][wallBreak] && map[tempY][tempX]==0){
                        visited[tempY][tempX][wallBreak] = true;
                        queue.add(new position(tempX,tempY,count+1, wallBreak,!time));
                    }
                    //인접한 벽을 만났을 때
                    else if(wallBreak<K && !visited[tempY][tempX][wallBreak+1] && map[tempY][tempX]==1){
                        if(time)	//낮일 때는 바로 이동, 거리 + 1
                            queue.add(new position(tempX,tempY,count+1, wallBreak+1, false));
                        else		//밤일 때는 한 번 기다렸다가 이동, 거리 + 2
                            queue.add(new position(tempX,tempY,count+2, wallBreak+1, false));
                        visited[tempY][tempX][wallBreak+1] = true;
                    }
                }
            }
        }
        return -1;		//도착 지점 도달 못했을 때 -1 반환
    }
}