https://www.acmicpc.net/problem/4179
4179번: 불!
입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문
www.acmicpc.net
분류 : BFS , DFS, 다익스트라 알고리즘
더보기
import java.io.*;
import java.math.*;
import java.util.*;
class MyScanner {
BufferedReader br;
StringTokenizer st;
public MyScanner() {
br = new BufferedReader(new InputStreamReader(System.in));
}
String next() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
long nextLong() {
return Long.parseLong(next());
}
double nextDouble() {
return Double.parseDouble(next());
}
}
public class Main {
public static PrintWriter out;
static int[] dx = { 0, -1, 0, 1 };
static int[] dy = { -1, 0, 1, 0 };
static char[][] maze;
static int[][] MoveTime, JohnTime;
static int R, C;
static int JHour, FHour;
static boolean check = false;
static final int inf = Integer.MAX_VALUE;
public static void main(String[] args) throws IOException {
MyScanner sc = new MyScanner();
out = new PrintWriter(new BufferedOutputStream(System.out));
R = sc.nextInt();
C = sc.nextInt();
maze = new char[R][C];
MoveTime = new int[R][C];
JohnTime = new int[R][C];
boolean FireCheck = false;
Queue<JPoint> John = new LinkedList<JPoint>();
Queue<FPoint> Fire = new LinkedList<FPoint>();
for (int r = 0; r < R; r++) {
String str = sc.next();
maze[r] = str.toCharArray();
}
for(int i=0;i<R;i++)
{
for(int j=0;j<C;j++)
{
MoveTime[i][j] = inf;
}
}
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
if (maze[i][j] == 'J') {
John.add(new JPoint(i, j));
JohnTime[i][j] = 0;
} else if (maze[i][j] == 'F') {
Fire.add(new FPoint(i, j));
FireCheck = true;
MoveTime[i][j] = 0;
}
}
}
FBFS(Fire);
JBFS(John);
if (check) {
System.out.println(JHour);
} else {
System.out.println("IMPOSSIBLE");
}
out.close();
}
private static void JBFS(Queue<JPoint> john) {
JHour = 1;
boolean[][] visited = new boolean[R][C];
loop1: while (!john.isEmpty()) {
int Jsize = john.size();
for (int sz = 0; sz < Jsize; sz++) {
JPoint Jp = john.poll();
int Jx = Jp.x;
int Jy = Jp.y;
visited[Jx][Jy] = true;
for (int ar = 0; ar < 4; ar++) {
int cx = Jx + dx[ar];
int cy = Jy + dy[ar];
if (cx >= 0 && cx < R && cy >= 0 && cy < C) {
if (maze[cx][cy] != '#' && maze[cx][cy] != 'F' && !visited[cx][cy]) {
if (MoveTime[cx][cy] > JohnTime[Jx][Jy] + 1) {
JohnTime[cx][cy] = JHour;
visited[cx][cy] = true;
john.add(new JPoint(cx, cy));
}
}
} else {
check = true;
break loop1;
}
}
}
JHour++;
}
}
private static void FBFS(Queue<FPoint> fire) {
FHour = 0;
boolean[][] visited = new boolean[R][C];
while (!fire.isEmpty()) {
int Fsize = fire.size();
for (int sz = 0; sz < Fsize; sz++) {
FPoint Fp = fire.poll();
int Fx = Fp.x;
int Fy = Fp.y;
visited[Fx][Fy] = true;
for (int ar = 0; ar < 4; ar++) {
int cx = Fx + dx[ar];
int cy = Fy + dy[ar];
if (cx >= 0 && cx < R && cy >= 0 && cy < C)
if (maze[cx][cy] != '#' && !visited[cx][cy]) {
MoveTime[cx][cy] = FHour + 1;
visited[cx][cy] = true;
fire.add(new FPoint(cx, cy));
}
}
}
FHour++;
}
}
}
class JPoint {
int x;
int y;
JPoint(int x, int y) {
this.x = x;
this.y = y;
}
}
class FPoint {
int x;
int y;
FPoint(int x, int y) {
this.x = x;
this.y = y;
}
}
이전 도전에는 시간 초과 맞고 포기했다가 1주일 만에 다시 도전해서 풀어내었다.
풀이 방식은 불의 움직임에 대한 bfs를 하여 시간을 저장해놓고
John이 그 보다 빠른 시간 내에 해당 지점에 갈 수 있는지 없는지 판단 그리고 탈출했는지 안 했는지 판단하여 결과를 출력한다.
꼭 풀고 싶었던 문제였기에 뿌듯하다!!!
P.S 03/31일 코드 문제점 발견으로 수정
'PS' 카테고리의 다른 글
[BOJ]1194번 : 달이 차오른다, 가자. (0) | 2017.03.31 |
---|---|
[BOJ]5427번 : 불 (0) | 2017.03.31 |
[BOJ]7569번 : 토마토 (0) | 2017.03.29 |
[BOJ]10974번 : 모든 순열 (0) | 2017.03.29 |
[BOJ]11657번 : 타임 머신 (0) | 2017.03.28 |