BOJ14442 벽부수고 이동하기2

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

14442번: 벽 부수고 이동하기 2

주의점!

벽부수고 이동하기1 과 달리 visited를 3중배열로 생성해야한다.

그 이유는 각 방문마다 벽을 1개 부시고 왔는지 2개 부시고 왔는지 다르기 때문이다.

import java.util.*;
import java.io.*;
public class Main
{   
    static int r;
    static int c;
    static int k;
    static int[][] map;
    
    public static int bfs(Node start){
        Queue<Node> q = new LinkedList();
        int[][][] visited = new int[r][c][k+1];
        int[] move_r = {1,-1,0,0};
        int[] move_c = {0,0,1,-1}; 
        q.offer(start);
        visited[start.r][start.c][0] = 1;
        while(q.size()>0){
            Node node = q.poll();
            if(node.r==r-1 && node.c==c-1){
                return node.step;
            }
            for(int i=0;i<4;i++){
                Node next = new Node(node.r+move_r[i], node.c+move_c[i],node.step+1,node.crash_count);
                
                if(next.r<0 || next.c<0 || next.r>=r || next.c>=c){
                    continue;
                }
                //벽일 경우 crash_count 검사후 수정후 큐 추가
                if(map[next.r][next.c]==1){
                    if(next.crash_count<k){
                        next.crash_count++;  
                        if( visited[next.r][next.c][next.crash_count]==1) continue;
                        q.offer(next);
                        visited[next.r][next.c][next.crash_count] = 1;
                    }
                    
                }
                //벽이 아닐 경우 큐에 추가
                if(map[next.r][next.c]==0){
                    if( visited[next.r][next.c][next.crash_count]==1) continue;
                    q.offer(next);
                    visited[next.r][next.c][next.crash_count] = 1;
                }
                
                
                
                
            }
        }
        return -1;
    }
    
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] input1= br.readLine().split(" ");
		r = Integer.parseInt(input1[0]);
		c = Integer.parseInt(input1[1]);
		k = Integer.parseInt(input1[2]);
		
		map = new int[r][c];
		
		for(int i=0; i<r;i++){
		    String[] input2 = br.readLine().split("");
		    for(int j=0;j<c;j++){
		        map[i][j] = Integer.parseInt(input2[j]);
		    }
		}
		
		
		System.out.println(bfs(new Node(0,0,1,0)));
		
	}
	
	public static class Node{
	    int r;
	    int c;
	    int step;
	    int crash_count;
	    
	    public Node(int r, int c, int step, int crash_count){
	        this.r=r;
	        this.c=c;
	        this.step=step;
	        this.crash_count= crash_count;
	    }
	}
}