[백준] 14442 벽 부수고 이동하기 2 - BFS + 방문처리 JAVA

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

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

코드설명

BFS 문제입니다. 

 

처음에는 벽 부수고 이동하기에서 그저 벽을 부순 경우와 아닌경우만 나누기 위해

visited[N][M][2]

위와 같이 2개의 경우만 나눠주었었는데,

 

아래와 같이 처리해야 합니다.

visited[N][M][K+1]

위와 같이 처리해야,  모든 경우를 탐색할 수 있습니다.

 

종료조건 처리하는경우, 처음에는 이동한곳에서 이후의 if(nr == N-1  이런식으로 nr 내에서 처리했지만, 이렇게 할경우

처음에 비어있는경우를 검사하지 못하므로, 종료처리를 처음에 해주었습니다. (물론, 다음 칸에서의 처리도  동시에 해도됩니다. 

1 1 4
0

https://www.acmicpc.net/board/view/113722

if(r == N-1 && c == M-1) {
    answer = moveCnt; 
    return ;
}

 

코드

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 Main {
	
	public static int N, M, K;
	public static char[][] map;
	public static boolean[][][] visited;
	public static int[] dx= {-1,1,0,0};
	public static int[] dy = {0,0,-1,1};
	public static int answer = 0;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	N = Integer.parseInt(st.nextToken());
    	M = Integer.parseInt(st.nextToken());
    	K = Integer.parseInt(st.nextToken());
    	
    	visited = new boolean[N][M][K+1];
    	map = new char[N][M];
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine());
    		map[i] = st.nextToken().toCharArray();
    	}
    	simulate();
    	if(answer == 0) {
    		System.out.println("-1");
    	}else {
    		System.out.println(answer);	
    	}
    	
    }
    
    public static void simulate() {
    	Queue<Node> q = new LinkedList<>();
    	q.offer(new Node(0, 0, 1, 0));
    	visited[0][0][0] = true;
    	while(!q.isEmpty()) {
    		Node temp = q.poll();
    		int r = temp.r;
    		int c = temp.c;
    		int moveCnt = temp.moveCnt;
    		int wallBreakCount = temp.wallBreakCount;
			if(r == N-1 && c == M-1) {
				answer = moveCnt; 
				return ;
			}    		
    		for(int dir=0;dir<4;dir++) {
    			int nr = r + dx[dir];
    			int nc = c + dy[dir];
    			
    			if(nr < 0 || nr >= N || nc < 0 || nc >= M) continue;
    			if(map[nr][nc] == '0') { //벽이 아닐경우 그냥 이동합니다. 
    				if(visited[nr][nc][wallBreakCount] == true) continue;
    				visited[nr][nc][wallBreakCount] = true;
    				q.offer(new Node(nr, nc, moveCnt + 1, wallBreakCount));
    			}
    			if(map[nr][nc] == '1') {
    				if(wallBreakCount >= K) continue; //이미 부술 수 있는 벽을 다 부쉈다면,
    				if(visited[nr][nc][wallBreakCount+1] == true) continue;
//    				map[nr][nc] = '0'; //변경할 필요없습니다.
    				visited[nr][nc][wallBreakCount + 1] = true;
    				q.offer(new Node(nr, nc, moveCnt + 1, wallBreakCount + 1));
    			}
    		}
    		
    		
    	}
    	
    }
    
}

class Node{
	int r;
	int c;
	int moveCnt;
	int wallBreakCount = 0;
	public Node(int r, int c, int moveCnt, int wallBreakCount) {
		this.r=r;
		this.c=c;
		this.moveCnt = moveCnt;
		this.wallBreakCount = wallBreakCount;
		
	}
}