[백준/Java] #5427 불
✏️ 불
사용 언어 : Java
레벨 : 골드 4
📎https://www.acmicpc.net/problem/5427
🔎 문제 설명
상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다.
매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에는 불이 붙지 않는다. 상근이는 동서남북 인접한 칸으로 이동할 수 있으며, 1초가 걸린다. 상근이는 벽을 통과할 수 없고, 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. 상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다.
빌딩의 지도가 주어졌을 때, 얼마나 빨리 빌딩을 탈출할 수 있는지 구하는 프로그램을 작성하시오.
📌 입력과 출력
입력
첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 최대 100개이다.
각 테스트 케이스의 첫째 줄에는 빌딩 지도의 너비와 높이 w와 h가 주어진다. (1 ≤ w,h ≤ 1000)
다음 h개 줄에는 w개의 문자, 빌딩의 지도가 주어진다.
- '.': 빈 공간
- '#': 벽
- '@': 상근이의 시작 위치
- '*': 불
각 지도에 @의 개수는 하나이다.
출력
각 테스트 케이스마다 빌딩을 탈출하는데 가장 빠른 시간을 출력한다. 빌딩을 탈출할 수 없는 경우에는 "IMPOSSIBLE"을 출력한다.
💻 입출력 예
⚒️ 풀이
문제를 보고 나서 BFS를 쓰면 된다는 것을 깨달아서 바로 BFS 코드를 짜기 시작했다. 다만, 문제점은 불의 BFS 와 상근이의 BFS를 동시에 돌려야한다는 점인데 전에 불! 문제를 풀었을 때와 조건이 비슷해서 불 BFS를 먼저 돌리고, 상근이의 BFS를 돌리면 풀 수 있는 문제였던 것 같다. 다른 BFS 문제와 다르게 크게 어려운 점은 없었는데, 아무래도 두 BFS를 동시에 돌려야 하다 보니 시간 안에 풀 수 있을지가 조금 걱정이 되었다. 일단 코드를 다 작성한뒤 예제 입출력과 같은 결과값이 나오는 것을 확인하고는 제출을 해봤다.
import java.io.*;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static class Pair {
int x;
int y;
public Pair(int x, int y) {
this.x = x;
this.y = y;
}
}
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
public static int bfs() throws IOException {
String[] input = br.readLine().split(" ");
int w = Integer.parseInt(input[0]);
int h = Integer.parseInt(input[1]);
String[][] building = new String[h][w];
Queue<Pair> person = new LinkedList<>(); // 상근 bfs
Queue<Pair> fire = new LinkedList<>(); // 불 bfs
int[][] move = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
for (int i = 0; i < h; i++) {
input = br.readLine().split("");
for (int j = 0; j < w; j++) {
if (input[j].equals("@")) {
person.add(new Pair(i, j));
} else if (input[j].equals("*")) {
fire.add(new Pair(i, j));
}
building[i][j] = input[j];
}
}
int time = 0;
while (!person.isEmpty() && !fire.isEmpty()) {
int fireSize = fire.size();
time++;
for (int k = 0; k < fireSize; k++) {
Pair cur = fire.poll();
for (int i = 0; i < 4; i++) {
int nx = cur.x + move[i][0];
int ny = cur.y + move[i][1];
if (nx < 0 || ny < 0 || nx >= h || ny >= w) continue;
if (building[nx][ny].equals("*") || building[nx][ny].equals("#")) continue;
building[nx][ny] = "*";
fire.add(new Pair(nx, ny));
}
}
int personSize = person.size();
for(int k = 0; k < personSize; k++) {
Pair cur = person.poll();
for (int i = 0; i < 4; i++) {
int nx = cur.x + move[i][0];
int ny = cur.y + move[i][1];
if(nx < 0 || ny < 0 || nx >= h || ny >= w) {
return time;
}
if(building[nx][ny].equals("*") || building[nx][ny].equals("#")) continue;
building[nx][ny] = "@";
person.add(new Pair(nx, ny));
}
}
}
return -1;
}
public static void main(String[] args) throws IOException {
int testCaseNum = Integer.parseInt(br.readLine());
for(int t = 0; t < testCaseNum; t++) {
int time = bfs();
bw.write(time == -1 ? "IMPOSSIBLE\n" : time + "\n");
}
bw.close();
}
}
결론은 메모리 초과가 나왔는데 코드를 분석한 결과, 크게 벗어나지는 않는 것 같아서 최대한 연산량을 줄일 수 있는 부분이 뭐가 있을지 찾아보다가
if(building[nx][ny].equals("*") || building[nx][ny].equals("#")) continue;
이 부분을 굳이 이렇게 할 필요가 없고 이동할 수 있는 땅이 아닌 경우만 찾으면 되지 않나? 싶어서
if(!building[nx][ny].equals(".")) continue;
이렇게 코드를 변경해주었더니 작동은 잘 했으나... 틀렸습니다. 가 나왔다. 내가 틀렸던 부분은 12% 였고 처음엔 반례를 나 혼자서 찾아보려고 이것저것 넣어봤었는데 잘 못찾겠어서 백준의 질문게시판을 이용하게 되었다.
생각보다 12%에서 틀리신 분이 많아서 반례는 쉽게 찾을 수 있었다.
10 5
##########
#@....#*.#
#.....#..#
#.....#..#
##.#######
바로 이 반례였는데 불은 벽에 가로막혀서 더 이상 이동하지 못하고 상근이는 계속 이동하다가 탈출을 하는 예제에서 정답은 5가 나와야하는데 내 코드의 경우 IMPOSSIBLE 이 나오는 상황이였다.
코드를 분석한 결과 while 문의 조건을 두 queue 가 비어있지 않는 상황에서만 bfs가 돌도록 코드를 짜버려서, 불의 BFS가 끝나니까 while문을 빠져나오게 되면서 time을 제대로 계산해도 마지막에 -1을 리턴하게 되는 것이였다.
while (!person.isEmpty() || !fire.isEmpty()) {
while 문 조건을 OR 문으로 변경하고 제출을 하니..!
맞았습니다!! 가 뜨는 모습!
생각보다 조금 헷갈렸던 문제인 것 같은데 BFS에 대해 잘 알고 있고 실수만 하지 않는다면 충분히 풀 수 있는 문제인 것 같다!
최종 코드
import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
static class Pair {
int x;
int y;
public Pair(int x, int y) {
this.x = x;
this.y = y;
}
}
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
public static int bfs() throws IOException {
String[] input = br.readLine().split(" ");
int w = Integer.parseInt(input[0]);
int h = Integer.parseInt(input[1]);
String[][] building = new String[h][w];
Queue<Pair> person = new LinkedList<>(); // 상근 bfs
Queue<Pair> fire = new LinkedList<>(); // 불 bfs
int[][] move = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
for (int i = 0; i < h; i++) {
input = br.readLine().split("");
for (int j = 0; j < w; j++) {
if (input[j].equals("@")) {
person.add(new Pair(i, j));
} else if (input[j].equals("*")) {
fire.add(new Pair(i, j));
}
building[i][j] = input[j];
}
}
int time = 0;
while (!person.isEmpty() || !fire.isEmpty()) {
int fireSize = fire.size();
time++;
for (int k = 0; k < fireSize; k++) {
Pair cur = fire.poll();
for (int i = 0; i < 4; i++) {
int nx = cur.x + move[i][0];
int ny = cur.y + move[i][1];
if (nx < 0 || ny < 0 || nx >= h || ny >= w) continue;
if (building[nx][ny].equals("*") || building[nx][ny].equals("#")) continue;
building[nx][ny] = "*";
fire.add(new Pair(nx, ny));
}
}
int personSize = person.size();
for(int k = 0; k < personSize; k++) {
Pair cur = person.poll();
for (int i = 0; i < 4; i++) {
int nx = cur.x + move[i][0];
int ny = cur.y + move[i][1];
if(nx < 0 || ny < 0 || nx >= h || ny >= w) {
return time;
}
if(!building[nx][ny].equals(".")) continue;
building[nx][ny] = "@";
person.add(new Pair(nx, ny));
}
}
}
return -1;
}
public static void main(String[] args) throws IOException {
int testCaseNum = Integer.parseInt(br.readLine());
for(int t = 0; t < testCaseNum; t++) {
int time = bfs();
bw.write(time == -1 ? "IMPOSSIBLE\n" : time + "\n");
}
bw.close();
}
}