공주님을 구해라! [백준 17836][골드5][Java]

 

[광고 누르면 오늘의 행운 상승!!]

 

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

17836번: 공주님을 구해라!

bfs 시뮬레이션 문제.

벽 뚫고 지나가기와 비슷한 문제이다.

포인트는 3차원 배열을 사용하여 검을 주웠을 때와 줍지 않았을 때의 visit처리를 따로 해주어야

서로의 경로가 겹치는 일이 없다.

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

class Hero{
	int row, col, time;
	int sword;
	public Hero(int row, int col, int sword, int time) {
		this.row = row;
		this.col = col;
		this.sword = sword;
		this.time = time;
	}
}
public class 공주님을구해라 {
	public static final int dx[] = {-1,0,1,0};
	public static final int dy[] = {0,1,0,-1};
	public static int map[][];
	public static boolean visit[][][];
	public static Queue<Hero> q;
	public static int N,M,T;
	
	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("test.txt"));
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		M = sc.nextInt();
		T = sc.nextInt();
		
		map = new int[N][M];
		visit = new boolean[2][N][M];
		q = new LinkedList<>();
		
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				map[i][j] = sc.nextInt();
				System.out.print(map[i][j]);
			}
			System.out.println();
		}
		int time = T;
		q.add(new Hero(0,0,0,time));
		visit[0][0][0] = true;
		
		bfs();
		System.out.println("Fail");
	}
	public static void bfs() {
		
		while(!q.isEmpty()) {
			Hero hero = q.poll();
			
			if(map[hero.row][hero.col] == 2) hero.sword = 1;
			
			if(hero.time == 0) {
				continue;
			}
			
			for (int i = 0; i < 4; i++) {
				int nx = hero.row + dx[i];
				int ny = hero.col + dy[i];
				
				if(nx < 0 || nx >= N || ny < 0 || ny >= M) {
					continue;
				}
				if(nx == N-1 && ny == M-1) {
					System.out.println(T-hero.time+1);
					System.exit(0);
				}
				if(visit[hero.sword][nx][ny]) {
					continue;
				}
				
				if(hero.sword == 1 && map[nx][ny] == 1) {
					visit[hero.sword][nx][ny] = true;
					q.add(new Hero(nx,ny,hero.sword,hero.time -1));
					continue;
				}
				
				if(map[nx][ny] == 0 || map[nx][ny] == 2) {
					visit[hero.sword][nx][ny] = true;
					q.add(new Hero(nx,ny,hero.sword,hero.time -1));
				}
				
			}
			
		}
	}

}