[백준BOJ] 16933번 벽 부수고 이동하기3.java

 

백준 저지에서 벽 부수고 이동하기3을 자바를 통해 풀어 보았다. 

 

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

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

 

16933번 벽 부수고 이동하기3.java

GitHub - tomy9729/Algorithm: 🐗 내가 직접 작성한 내 코드 🐗

 

16933번 벽 부수고 이동하기3

문제

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다. 이동하지 않고 같은 칸에 머물러있는 경우도 가능하다. 이 경우도 방문한 칸의 개수가 하나 늘어나는 것으로 생각해야 한다.
이번 문제에서는 낮과 밤이 번갈아가면서 등장한다. 가장 처음에 이동할 때는 낮이고, 한 번 이동할 때마다 낮과 밤이 바뀌게 된다. 이동하지 않고 같은 칸에 머무르는 경우에도 낮과 밤이 바뀌게 된다.
만약에 이동하는 도중에 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 K개 까지 부수고 이동하여도 된다. 단, 벽은 낮에만 부술 수 있다.
한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.
맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.

설명

벽 부수고 이동하기2 문제에 이어지는 문제이다. 

 

낮과 밤이라는 조건이 추가되었다. 밤일 경우 벽을 부술 수 없으며, 이동하지 않는 경우도 추가되었다. 

 

먼저 이동하지 않는 경우를 생각해본다. 벽을 만나서 부수고 싶지만 밤일 경우 이동하지 않을 것이다. 따라서 이 경우 방문 체크는 하지 않으면서 이동 수만 올려야한다. 

 

가만히 있으면서 이동 수만 올리기 위해 기존 코드에서 position 클래스를 약간 수정하였다. position 클래스에서 이동 수를 저장하도록 했다. visit 배열은 boolean으로 바꿔서 방문 체크만 하도록 했다. 

 

벽이 없다면 그대로 진행한다. 벽이 있다면 낮과 밤을 구분한다. 낮이라면 부술 것이고 밤이라면 대기한다.

코드

//16933번 벽 부수고 이동하기3.java
package boj20211215;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class 벽_부수고_이동하기3_16933 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();
    
    static class position{
    	int i;
    	int j;
    	int wall;
    	boolean day;
    	int cnt;
    	position(int i, int j, int wall, boolean day, int cnt) {
			this.i=i;
			this.j=j;
			this.wall=wall;
			this.day=day;
			this.cnt=cnt;
		}
    }
    public static void main(String[] args) throws IOException {
		st = new StringTokenizer(br.readLine()," ");
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		
		int[][] map = new int[N+1][M+1];
		boolean[][][] visit = new boolean[N+1][M+1][K+1];
		
		for(int i=1;i<=N;i++) {
			String line = br.readLine();
			for(int j=1;j<=M;j++) {
				map[i][j] = Integer.parseInt(line.substring(j-1,j));
			}
		}
		
		bfs(map, visit, new position(1, 1, 0, true,1),N,M,K);
		
	}
    
    static void bfs(int[][]map, boolean[][][] visit, position start, int N, int M, int K) {
    	int[] di = {1,-1,0,0};
    	int[] dj = {0,0,1,-1};
    	Queue<position> q = new LinkedList<position>();
    	q.add(start);
    	visit[start.i][start.j][start.wall]=true;
    	while(!q.isEmpty()) {
    		position now = q.poll();
    		if(now.i==N && now.j==M) {
    			System.out.println(now.cnt);
    			return;
    		}
    		for(int d=0;d<4;d++) {
    			int i = now.i+di[d];
    			int j = now.j+dj[d];
    			int w = now.wall;
    			boolean day = now.day;
    			
    			if(1<=i && i<=N && 1<=j && j<=M) {
    				if(map[i][j]==0 && !visit[i][j][w]) {
        				//벽이 아닌 경우
        				visit[i][j][w] = true;
        				q.add(new position(i, j, w,!day,now.cnt+1));
        			}
    				
        			if(map[i][j]==1 && w<K) {
        				//벽이지만 부술 수 있는 경우
        				//낮일 경우
        				if(day && !visit[i][j][w+1]) {
        					visit[i][j][w+1] = true;
            				q.add(new position(i, j, w+1,!day,now.cnt+1));
        				}
        				//밤일 경우
        				//낮이 되기를 기다렸다가 부심
        				else if(!day && !visit[i][j][w+1]){
            				q.add(new position(now.i, now.j, w,!day,now.cnt+1));
        				}
        			}
    			}
    		}
    	}
    	System.out.println(-1);
    }
}