[백준] 17836 공주님을 구해라! - BFS JAVA

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

17836번: 공주님을 구해라!

 

 

문제풀이

BFS 문제에 '검' 이라는 조건이 하나 더 있는 문제였습니다.

처음 봤을때 '검' 이 있을떄와 '검' 이 없을때 다르게 조건을 세워서 두번 BFS를 구해야하나 이런생각을 했었습니다.

이 문제 같은경우 Visited[][][0] ( 검이 없을 때 ) Visited[][][1] ( 검이 있을 때) 이렇게 두가지 방문배열을 만들어서 사실상 BFS를 두번 돌립니다. 

조건에 따라서 BFS를 두번 사용하기 위해 Visited[N][M][0,1] 방문배열을 두개 만든다는 생각을 하면 풀 수 있습니다.

 

코드입니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
	public static int N, M, T;
	public static int[][] map;
	public static int result=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());
    	T = Integer.parseInt(st.nextToken());
    	
    	map = new int[N][M];
    	for(int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine());
    		for(int j=0;j<M;j++) {
    			map[i][j] = Integer.parseInt(st.nextToken()); 
    		}
    	}
    	
    	BFS();
    	
    	if(result <= T && result > 0) {
    		System.out.println(result);
    	}else if(result == 0 || result > T){
    		System.out.println("Fail");
    	}

    } 
    
    public static void BFS() {
    	int[] dx = {-1,1,0,0};
    	int[] dy = {0,0,-1,1};
    	boolean[][][] visited = new boolean[N][M][2];
    	Queue<Node> q = new LinkedList<>();
    	q.offer(new Node(0, 0, 0, false));
    	visited[0][0][0] = true;
    	
    	while(!q.isEmpty()) {
    		Node temp = q.poll();
    		int x = temp.x;
    		int y = temp.y;
    		int cnt = temp.cnt;
    		boolean sword = temp.sword;
    		
    		if(x == N -1 && y == M - 1) {
    			result = cnt;
    			return ;
    		}
    		
    		for(int dir=0;dir<4;dir++) {
    			int nx = x + dx[dir];
    			int ny = y + dy[dir];
    			
    			if( nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
    			
    			//칼이 있을시 분기
    			if( sword == true) {
    				//칼이 있다면 벽을 뚫을 수 있습니다.
        			//칼이 있다면 visited[][][1] 배열로 확인합니다.
        			if( visited[nx][ny][1] == true) continue;
        			
    				q.offer(new Node(nx, ny, cnt + 1 , true));
    				visited[nx][ny][1] = true;
    			}
    			
    			//칼이 없을시 분기
    			else if( sword == false){
    				
    				//칼이 없다면 벽을 못뚫습니다.
        			if( map[nx][ny] == 1 )continue;
        			
        			//칼이 없다면 visited[][][0] 배열로 확인합니다.
        			if( visited[nx][ny][0] == true) continue;
        		
        			if( map[nx][ny] == 0 ) {
        				q.offer(new Node(nx, ny, cnt + 1 , false));
        				visited[nx][ny][0] = true;
        			} else if( map[nx][ny] == 2 ) {
        				q.offer(new Node(nx, ny, cnt + 1 , true));
        				visited[nx][ny][0] = true;
        				visited[nx][ny][1] = true;
        				
        			}
    			}	
    		}
    		
    	}
    	
    	
    	
    	
    }
    
    
}

class Node{
	int x;
	int y;
	int cnt;
	boolean sword;
	public Node(int x, int y, int cnt, boolean sword) {
		this.x=x;
		this.y=y;
		this.cnt=cnt;
		this.sword = sword;
	}
}