알고리즘
[백준/Java] #4179 불! (⚠️시행착오 엄청 많음 주의⚠️)
하늘☁️
2023. 5. 18. 19:04
오늘은 피코 스터디에서 BFS 문제들을 풀고 코드리뷰 하는 시간을 가졌다. 다른 BFS 문제는 큰 고난 없이 잘 풀었는데 나의 멘탈을 탈탈 털게 해 준 문제가 있어서 들고 와봤다.
[백준 - #4179] 불!
4179번: 불!
입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문자
www.acmicpc.net
✔️ 문제 설명
지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자!미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기 전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야 한다. 지훈이와 불은 매 분마다 한 칸씩 수평 또는 수직으로(비스듬하게 이동하지 않는다) 이동한다. 불은 각 지점에서 네 방향으로 확산된다. 지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다. 지훈이와 불은 벽이 있는 공간은 통과하지 못한다.
입력
입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문자들은 다음을 뜻한다.#: 벽.: 지나갈 수 있는 공간 J: 지훈이의 미로에서의 초기위치 (지나갈 수 있는 공간) F: 불이 난 공간 J는 입력에서 하나만 주어진다.
출력
지훈이가 불이 도달하기 전에 미로를 탈출 할 수 없는 경우 IMPOSSIBLE을 출력한다. 지훈이가 미로를 탈출할 수 있는 경우에는 가장 빠른 탈출시간을 출력한다.
🚩 시행 착오
이제 막 바킹독 알고리즘으로 BFS를 배우면서 이 문제를 접하게 된 것이었는데 처음에 봤을 때는 어? 그냥 동시에 돌리면 되겠네! 하고 슉슉 풀다가 막히기 시작하면서 점점 멘탈을 잡기가 힘들었다.
우선 이 문제는 BFS를 사용하는 문제로 전형적인 BFS 문제들에 불이라는 조건이 추가된 것이다. 그리고 지훈이가 불이 퍼지기 전에 미로를 탈출할 수 있는 최소 시간을 구하는 문제인데 우선 처음에 main 메서드에서 입출력을 받기 전에 지훈이의 시작 위치와 불의 시작 위치를 담은 배열을 각각 선언해 주었다.
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
int[][] maze = new int[x][y];
int[] JStart = new int[2];
int[] fireStart = new int[2];그리고 입출력을 받으면서 '#' 일 경우 미로 칸을 1로 초기화하고, 'J'일 경우 JStart라는 지훈이의 시작 위치 배열에 저장하고 'F'일 경우 불의 시작 위치 배열에 저장한 뒤 BFS 메서드를 호출해서 BFS를 실행하도록 하고 미로 배열과 지훈이 시작위치 배열, 불의 시작 위치 배열을 매개변수로 넘겨주었다.
for(int i = 0; i < x; i++) {
String[] input = br.readLine().split("");
for(int j = 0; j < y; j++) {
if (!input[j].equals("#")) {
maze[i][j] = 1;
if(input[j].equals("J")) {
JStart[0] = i;
JStart[1] = j;
} else if (input[j].equals("F")) {
fireStart[0] = i;
fireStart[1] = j;
}
}
}
}
Main result = new Main();
bw.write(result.solution(maze, JStart, fireStart));
bw.close();이후 나는 불 BFS를 먼저 돌리고 나서 그 퍼지는 시간을 기준으로 지훈이의 BFS를 돌리면 정답을 구할 수 있을 것 같아서 먼저 미로에 불이 각 칸에 퍼지는 시간을 저장한 배열과 불 BFS를 하기 위한 불의 방문 배열을 선언하고 시작 위치 배열을 이용해 불의 시작 위치에 방문했다는 표시를 남기고 큐에 담아주었다.
지금 보니까 왜 굳이 좌표를 배열로 저장했는지 모르겠지만.. 이 때는 일단 어떻게든 풀고 보자! 였어서 별로 신경을 쓰지 않은 듯하다.
여튼 큐가 빌 때까지 while 문을 돌리면서 큐에 있는 값을 빼고, 상하좌우를 확인했을 때 불이 방문한 적이 없고, 미로가 1이 아니면 (= 벽이 아닐 때) 큐에 넣어 주고, 방문 표시를 하고, 큐에서 빼온 위치의 값에 +1을 해줘서 불이 상하좌우로 퍼질 때마다 1씩 증가하도록 BFS를 돌렸다.
int[] dx = {1, 0, -1, 0};
int[] dy = {0, 1, 0, -1};
Queue<ArrayList<Integer>> queue = new LinkedList<>();
int[][] fireMaze = new int[maze.length][maze[0].length]; // 미로에 불이 퍼지는 시간 계산한 배열
boolean[][] visit = new boolean[maze.length][maze[0].length]; // 불 BFS를 하기위한 방문 배열
visit[fireStart[0]][fireStart[1]] = true;
queue.add(new ArrayList<Integer>(Arrays.asList(fireStart[0], fireStart[1])));
while (!queue.isEmpty()) {
ArrayList<Integer> cur = queue.poll();
for(int i = 0; i < 4; i++) {
int nx = cur.get(0) + dx[i];
int ny = cur.get(1) + dy[i];
if(nx < 0 || nx >= maze.length || ny < 0 || ny >= maze[0].length) continue;
if(visit[nx][ny] || maze[nx][ny] != 1) continue;
queue.add(new ArrayList<Integer>(Arrays.asList(nx, ny)));
visit[nx][ny] = true;
fireMaze[nx][ny] = fireMaze[cur.get(0)][cur.get(1)] + 1;
}
}이후 지훈이의 시간을 계산한 배열과 미로 방문 배열을 선언하고 BFS를 위와 동일한 방식으로 돌렸는데, 불 BFS와 다르게 조건이 하나가 추가되었다. 큐에서 빼낸 값에 +1 한 값(이동하고 난 후의 이동 횟수)이 그 칸에 불이 퍼지는 데 걸리는 시간과 같거나 크면 그전에 불이 도착을 해서 못 가는 곳이니까 그 조건에 해당하지 않는 칸만 큐에서 추가해 주고 방문 표시를 해주었다.
큐에서 빼낸 값의 상하좌우가 배열 범위를 넘어갔다는 것은 탈출에 성공했음을 의미하니까 그때 큐에서 빼온 값에 +1 (자기 자신을 포함하기 위한 +1)을 리턴해주었다.
만약 반복문이 전부 다 끝났음에도 범위를 넘어간 적이 없다는 것은 지훈이가 미로의 가장자리로 올 수 없다는 뜻이니까 불가능이라는 문자열을 리턴해주도록 하였다.
int[][] JMaze = new int[maze.length][maze[0].length]; // 지훈이의 시간 계산한 배열
visit = new boolean[maze.length][maze[0].length]; // 지훈이의 미로 방문 배열
visit[JStart[0]][JStart[1]] = true;
queue.add(new ArrayList<Integer>(Arrays.asList(JStart[0], JStart[1])));
while (!queue.isEmpty()) {
ArrayList<Integer> cur = queue.poll();
for(int i = 0; i < 4; i++) {
int nx = cur.get(0) + dx[i];
int ny = cur.get(1) + dy[i];
// 범위를 넘어가는 것은 탈출에 성공했음을 의미
if(nx < 0 || nx >= maze.length || ny < 0 || ny >= maze[0].length) {
return String.valueOf(JMaze[cur.get(0)][cur.get(1)] + 1);
}
if(visit[nx][ny] || maze[nx][ny] != 1 || JMaze[cur.get(0)][cur.get(1)] + 1 >= fireMaze[nx][ny]) continue;
queue.add(new ArrayList<Integer>(Arrays.asList(nx, ny)));
visit[nx][ny] = true;
JMaze[nx][ny] = JMaze[cur.get(0)][cur.get(1)] + 1;
}
}
return "IMPOSSIBLE";
전체 코드
import java.io.*;
import java.util.*;
public class Main {
public String solution(int[][] maze, int[] JStart, int[] fireStart) {
int[] dx = {1, 0, -1, 0};
int[] dy = {0, 1, 0, -1};
Queue<ArrayList<Integer>> queue = new LinkedList<>();
int[][] fireMaze = new int[maze.length][maze[0].length]; // 미로에 불이 퍼지는 시간 계산한 배열
boolean[][] visit = new boolean[maze.length][maze[0].length]; // 불 BFS를 하기위한 방문 배열
visit[fireStart[0]][fireStart[1]] = true;
queue.add(new ArrayList<Integer>(Arrays.asList(fireStart[0], fireStart[1])));
while (!queue.isEmpty()) {
ArrayList<Integer> cur = queue.poll();
for(int i = 0; i < 4; i++) {
int nx = cur.get(0) + dx[i];
int ny = cur.get(1) + dy[i];
if(nx < 0 || nx >= maze.length || ny < 0 || ny >= maze[0].length) continue;
if(visit[nx][ny] || maze[nx][ny] != 1) continue;
queue.add(new ArrayList<Integer>(Arrays.asList(nx, ny)));
visit[nx][ny] = true;
fireMaze[nx][ny] = fireMaze[cur.get(0)][cur.get(1)] + 1;
}
}
int[][] JMaze = new int[maze.length][maze[0].length]; // 지훈이의 시간 계산한 배열
visit = new boolean[maze.length][maze[0].length]; // 지훈이의 미로 방문 배열
visit[JStart[0]][JStart[1]] = true;
queue.add(new ArrayList<Integer>(Arrays.asList(JStart[0], JStart[1])));
while (!queue.isEmpty()) {
ArrayList<Integer> cur = queue.poll();
for(int i = 0; i < 4; i++) {
int nx = cur.get(0) + dx[i];
int ny = cur.get(1) + dy[i];
// 범위를 넘어가는 것은 탈출에 성공했음을 의미
if(nx < 0 || nx >= maze.length || ny < 0 || ny >= maze[0].length) {
return String.valueOf(JMaze[cur.get(0)][cur.get(1)] + 1);
}
if(visit[nx][ny] || maze[nx][ny] != 1 || JMaze[cur.get(0)][cur.get(1)] + 1 >= fireMaze[nx][ny]) continue;
queue.add(new ArrayList<Integer>(Arrays.asList(nx, ny)));
visit[nx][ny] = true;
JMaze[nx][ny] = JMaze[cur.get(0)][cur.get(1)] + 1;
}
}
return "IMPOSSIBLE";
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
int[][] maze = new int[x][y];
int[] JStart = new int[2];
int[] fireStart = new int[2];
for(int i = 0; i < x; i++) {
String[] input = br.readLine().split("");
for(int j = 0; j < y; j++) {
if (!input[j].equals("#")) {
maze[i][j] = 1;
if(input[j].equals("J")) {
JStart[0] = i;
JStart[1] = j;
} else if (input[j].equals("F")) {
fireStart[0] = i;
fireStart[1] = j;
}
}
}
}
Baekjoon4179 result = new Baekjoon4179();
bw.write(result.solution(maze, JStart, fireStart));
bw.close();
}
}
하지만 11%에서 댕같이 실패했다. 테스트 케이스는 성공하고 다른 케이스도 내가 직접 넣어보았는데 문제가 없는 것 같아서 반례를 찾기로 했다. 어디서 문제일지 도저히 모르겠어서 백준 질문 게시판을 이용했고 그 결과 고수님께서 반례를 찾아주셨다.
input:
5 5
#####
#F#J#
###.#
###.#
###.#
output : IMPOSSIBLE
answer : 4실제로 반례를 돌려보니 4가 아닌 IMPOSSIBLE이 출력되는 것을 확인했다.
// 메인에서 입력받을 때 #만 미로에서 1로 바꿔주고 나머지는 다 0으로 초기화 되어 있음
if (!input[j].equals("#")) {
maze[i][j] = 1;
}
// 이 코드에서 문제 발생
if(visit[nx][ny] || maze[nx][ny] != 1 || JMaze[cur.get(0)][cur.get(1)] + 1 >= fireMaze[nx][ny]) continue;이 이유가 처음에 나는 #일 때만 1로 초기화를 하고 미로의 나머지는 전부 0으로 초기화가 되어있는 상태였다.
BFS에서 지훈이의 BFS를 수행할 때 지훈이가 이동한 칸이 불이 이동하는 데 걸리는 시간보다 크거나 같으면 움직일 수 없도록 구현을 했기 때문에 지훈이가 불이 방문하지 않은 칸임에도 0이어서 이동할 수가 없는 것이다. 그래서 이 코드를 수정하기 위해 미로의 값이 '.' 일 때 불의 이동 배열을 Integer.MAX_VALUE로 전부 초기화해주었다.
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
// 입출력 받기
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int R = Integer.parseInt(st.nextToken());
int C = Integer.parseInt(st.nextToken());
String[][] maze = new String[R][C];
for(int i = 0; i < R; i++) {
String[] s = br.readLine().split("");
for(int j = 0; j < C; j++) {
maze[i][j] = s[j];
}
}
Main result = new Main();
bw.write(result.BFS(maze));
bw.close();
}
public String BFS(String[][] maze) {
int[] dx = {1, 0, -1, 0};
int[] dy = {0, 1, 0, -1};
// 불의 퍼지는 시간을 담는 배열
int[][] distFire = new int[maze.length][maze[0].length];
// 지훈이의 탈출 시간을 담은 배열
int[][] distJ = new int[maze.length][maze[0].length];
// 불의 시작 지점
Pair fireStart = null;
// 지훈이 시작 지점
Pair JStart = null;
// BFS를 하기위해 시작 지점 구하기
for(int i = 0; i < maze.length; i++) {
for(int j = 0; j < maze[0].length; j++) {
if(maze[i][j].equals("J")) {
JStart = new Pair(i, j);
distJ[i][j] = 1;
distFire[i][j] = Integer.MAX_VALUE;
} else if(maze[i][j].equals("F")) {
fireStart = new Pair(i, j);
// 나중에 이동 경로에 #(벽)이 있으면 못가도록 할건데 불의 시작위치는 #이 아니니까 불의 시작 위치로도 가게 됨
// 불의 위치로는 갈 수 없으니 좌표만 구하고 벽으로 바꿔줌
maze[i][j] = "#";
distFire[i][j] = 1;
} else if(maze[i][j].equals(".")) {
// 그 칸에 지훈이 이동 횟수 >= 불의 이동 횟수일 경우 움직이지 않도록
// 초기 값을 MAX 값으로 설정
distFire[i][j] = Integer.MAX_VALUE;
}
}
}
Queue<Pair> queue = new LinkedList();
queue.offer(fireStart);
// 불의 BFS
while (!queue.isEmpty()) {
Pair cur = queue.poll();
for(int i = 0; i < 4; i++) {
int nx = cur.x + dx[i];
int ny = cur.y + dy[i];
if (nx < 0 || nx >= maze.length || ny < 0 || ny >= maze[0].length) continue;
if(distFire[nx][ny] != Integer.MAX_VALUE || maze[nx][ny].equals("#")) continue;
queue.offer(new Pair(nx, ny));
distFire[nx][ny] = distFire[cur.x][cur.y] + 1;
}
}
// 어차피 큐에 아무것도 안들어있으니까 지훈이의 BFS를 큐 재사용
queue.offer(JStart);
// 지훈이의 BFS
while (!queue.isEmpty()) {
Pair cur = queue.poll();
for(int i = 0; i < 4; i++) {
int nx = cur.x + dx[i];
int ny = cur.y + dy[i];
// 범위를 벗어났다는 것은 탈출했다는 것이니까 전 값을 바로 리턴해줌
if (nx < 0 || nx >= maze.length || ny < 0 || ny >= maze[0].length) {
return String.valueOf(distJ[cur.x][cur.y]);
}
// 그 전값에서 +1 한게 fire의 퍼지는 시간보다 같거나 크면 갈 수 없는 길
if(distJ[nx][ny] > 0 || maze[nx][ny].equals("#") || distJ[cur.x][cur.y] + 1 >= distFire[nx][ny]) continue;
distJ[nx][ny] = distJ[cur.x][cur.y] + 1;
queue.offer(new Pair(nx, ny));
}
}
return "IMPOSSIBLE";
}
public static class Pair {
int x;
int y;
public Pair(int x, int y) {
this.x = x;
this.y = y;
}
}
}
코드를 다시 작성하면서 어차피 불이 갈 수 있는 길은 전부 MAX 값으로 초기화해뒀으니 불이 이동한다면 MAX 값이 아닌 1, 2, 3과 같은 이동 값이 담길 것이고 이 값이 담겼다는 것은 이미 방문했다는 뜻이니까 이번엔 굳이 방문 배열을 선언하지 않았다.
또한 이때 좌표 배열을 굳이 선언할 필요가 없는 것을 깨닫고 다시 작성할 때는 좌표 배열을 선언하지 않았다. 필요 없는 부분을 제거한 것만 제외하면 위의 코드랑 크게 다를 것은 없다.
이후 반례를 돌려보니 이번엔 원하는 값이 잘 나오는 것을 확인할 수 있었다.
하지만...............
똑같이 11%에서 통과가 되지 못했다. 그렇다. 나는 11%의 굴레에서 빠져나오지 못했다.
이번에도 뭐가 문제일까 싶어서 계속해서 다른 케이스들을 넣어보고 백준 질문게시판에 있는 다른 반례들도 넣어봤는데 기댓값으로 잘 출력되었었다. 도대체 뭐가 문제야..?
그래서 결국.... 처음부터 다시 짜자! 누가 이기나 해보자..! 하면서 코드를 아예 뒤엎기 시작했습니다.
import java.io.*;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static String[][] maze;
static int[][] jihunDist;
static int[][] fireDist;
static Pair jihunStart;
static Pair fireStart;
public static void main(String[] args) throws IOException {
// 입출력 받기
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int R = Integer.parseInt(st.nextToken());
int C = Integer.parseInt(st.nextToken());
maze = new String[R][C];
for(int i = 0; i < R; i++) {
String[] s = br.readLine().split("");
for(int j = 0; j < C; j++) {
if(s[j].equals("J")) jihunStart = new Pair(i, j);
else if(s[j].equals("F")) fireStart = new Pair(i, j);
maze[i][j] = s[j];
}
}
Main result = new Main();
bw.write(result.BFS());
bw.close();
}
public String BFS() {
int[][] dist = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
// 지훈이의 큐와 불의 큐를 각각 선언
Queue<Pair> jihunQue = new LinkedList<>();
Queue<Pair> fireQue = new LinkedList<>();
// 각 시작 지점을 큐에 넣어줌
jihunQue.offer(new Pair(jihunStart.x, jihunStart.y));
fireQue.offer(new Pair(fireStart.x, fireStart.y));
// 지훈이와 불의 이동 횟수를 담은 배열 선언
jihunDist = new int[maze.length][maze[0].length];
fireDist = new int[maze.length][maze[0].length];
// 지훈이의 이동 횟수가 불의 이동 횟수보다 같거나, 크면 이동하지 못하게 하도록
// 불의 이동횟수 전체를 int MAX 값으로 설정
for(int[] row : fireDist) {
Arrays.fill(row, Integer.MAX_VALUE);
}
// 초기 위치 1로 설정
jihunDist[jihunStart.x][jihunStart.y] = 1;
fireDist[fireStart.x][fireStart.y] = 1;
while (!jihunQue.isEmpty()) {
int fireN = fireQue.size();
int jihunN = jihunQue.size();
for(int i = 0; i < fireN; i++) {
Pair fireCur = fireQue.poll();
for(int j = 0; j < 4; j++) {
int nx = fireCur.x + dist[j][0];
int ny = fireCur.y + dist[j][1];
if(nx < 0 || nx >= maze.length || ny < 0 || ny >= maze[0].length) continue;
if(fireDist[nx][ny] != Integer.MAX_VALUE || maze[nx][ny].equals("#")) continue;
fireDist[nx][ny] = fireDist[fireCur.x][fireCur.y] + 1;
fireQue.offer(new Pair(nx, ny));
}
}
for(int i = 0; i < jihunN; i++) {
Pair jihunCur = jihunQue.poll();
for(int j = 0; j < 4; j++) {
int nx = jihunCur.x + dist[j][0];
int ny = jihunCur.y + dist[j][1];
if(nx < 0 || nx >= maze.length || ny < 0 || ny >= maze[0].length) {
return String.valueOf(jihunDist[jihunCur.x][jihunCur.y]);
}
if(jihunDist[nx][ny] > 0 || fireDist[nx][ny] != Integer.MAX_VALUE || maze[nx][ny].equals("#")) continue;
jihunDist[nx][ny] = jihunDist[jihunCur.x][jihunCur.y] + 1;
jihunQue.offer(new Pair(nx, ny));
}
}
}
return "IMPOSSIBLE";
}
public static class Pair {
int x;
int y;
public Pair(int x, int y) {
this.x = x;
this.y = y;
}
}
}새로 짠 코드인데 그냥 지훈이의 큐가 빌 때까지 while문을 돌리면서 한 번에 불이 먼저 한 칸씩 퍼지고, 지훈이 이동하고, 불 한칸씩 퍼지고, 지훈이 이동하고 하면서 지훈이가 이동했을 때 거기에 이미 불이 퍼져있다면 지나가지 않는 로직으로 다시 짰다.
나머지 부분은 위의 코드랑 거의 비슷하다. 이번에도 역시 반례들을 다 돌려보고 잘 돌아가길래 아 진짜 이거다! 잘 짰다 했는데..
ㅋㅋ.ㅋ.. 똑같이 11%에서 멈추는 것이 아닌가..
💡 풀이
결국 스터디원들과 코드리뷰 하기 전까지 풀지 못했다. 코드리뷰를 하면서 통과한 다른 팀원들의 코드를 보면서 왜 나만 안되는 거야.. 하면서 괴로운 리뷰 시간을 가졌다. (괴로운 건 아니고 사실 화가 단단히 남) 리뷰가 끝나고 통과하지 못한 코드들에 대해 분석하는 시간을 가지면서 나도 내 코드를 조금씩 수정해 보기로 했다.
사실 통과한 코드랑 내 코드랑 크게 다른 점을 못 느끼겠어서 우선 다들 변수를 전역변수로 선언했길래 나도 일부만 전역변수로 선언했던 것을 전부 전역변수로 바꿔주었다. 물론 로직에 변화가 없으니 결괏값은 그대로 나오겠고, 백준에 제출 한 번 해보자 하면서 제출을 해봤는데
🤔🤔🤔🤔🤔🤔🤔🤔🤔🤔🤔
갑자기 되는 것이었다... 왜.. 왜????????????????????
통과한 코드
import java.io.*;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static String[][] maze;
static int[][] jihunDist;
static int[][] fireDist;
// 지훈이의 큐와 불의 큐를 각각 선언
static Queue<Pair> jihunQue = new LinkedList<>();
static Queue<Pair> fireQue = new LinkedList<>();
public static void main(String[] args) throws IOException {
// 입출력 받기
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int R = Integer.parseInt(st.nextToken());
int C = Integer.parseInt(st.nextToken());
maze = new String[R][C];
// 지훈이와 불의 이동 횟수를 담은 배열 선언
jihunDist = new int[R][C];
fireDist = new int[R][C];
// 지훈이의 이동 횟수가 불의 이동 횟수보다 같거나, 크면 이동하지 못하게 하도록
// 불의 이동횟수 전체를 int MAX 값으로 설정
for(int[] row : fireDist) {
Arrays.fill(row, Integer.MAX_VALUE);
}
for(int i = 0; i < R; i++) {
// 각 시작 지점을 큐에 넣어줌
String[] s = br.readLine().split("");
for(int j = 0; j < C; j++) {
if(s[j].equals("J")) {
jihunDist[i][j] = 1;
jihunQue.offer(new Pair(i, j));
}
else if(s[j].equals("F")) {
fireDist[i][j] = 1;
fireQue.offer(new Pair(i, j));
}
maze[i][j] = s[j];
}
}
Main result = new Main();
bw.write(result.BFS());
bw.close();
}
public String BFS() {
int[][] dist = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
while (!jihunQue.isEmpty()) {
int fireN = fireQue.size();
int jihunN = jihunQue.size();
for(int i = 0; i < fireN; i++) {
Pair fireCur = fireQue.poll();
for(int j = 0; j < 4; j++) {
int nx = fireCur.x + dist[j][0];
int ny = fireCur.y + dist[j][1];
if(nx < 0 || nx >= maze.length || ny < 0 || ny >= maze[0].length) continue;
if(fireDist[nx][ny] != Integer.MAX_VALUE || maze[nx][ny].equals("#")) continue;
fireDist[nx][ny] = fireDist[fireCur.x][fireCur.y] + 1;
fireQue.offer(new Pair(nx, ny));
}
}
for(int i = 0; i < jihunN; i++) {
Pair jihunCur = jihunQue.poll();
for(int j = 0; j < 4; j++) {
int nx = jihunCur.x + dist[j][0];
int ny = jihunCur.y + dist[j][1];
if(nx < 0 || nx >= maze.length || ny < 0 || ny >= maze[0].length) {
return String.valueOf(jihunDist[jihunCur.x][jihunCur.y]);
}
if(jihunDist[nx][ny] > 0 || fireDist[nx][ny] != Integer.MAX_VALUE || maze[nx][ny].equals("#")) continue;
jihunDist[nx][ny] = jihunDist[jihunCur.x][jihunCur.y] + 1;
jihunQue.offer(new Pair(nx, ny));
}
}
}
return "IMPOSSIBLE";
}
public static class Pair {
int x;
int y;
public Pair(int x, int y) {
this.x = x;
this.y = y;
}
}
}
사실 아직까지도 갑자기 왜 됐는지 잘 모르겠다. 로직은 건들지 않았는데.. 입출력 문제였던 것일까 ㅠㅠ..?
혹시 문제를 아시는 고수 분이 계시다면 댓글로 좀 알려주세요...
포기하지 않고 풀어낸 것이 뿌듯하기도 한데 좀 허탈하다.. 난 뇌가 없는 걸까..? 라며 괴로워했는데..
그래도 잘 풀어내서 다행이다. 많은 시행착오를 겪으면서 BFS에 대해 더 깊게 알게 된 것 같다! 다음에 다시 한번 더 풀어보면서 절대 까먹지 않도록..✊🏻