📜 문제
- 미로 (2차원 배열)에
#,.,J,F문자가 주어짐 - J는 하나만 주어지고 F는 여러개가 주어질 수 있음
- 미로의 상태가 주어졌을 때 지훈이가 탈출할 수 있는 최소 시간 찾기
- 탈출할 수 없는 경우
IMPOSSIBLE출력
BFS로 풀 수 있는 문제이다.
기존에 한 가지 요소만 이동하는 BFS 문제와 달리,동시에 두 가지 요소의 BFS를 수행해야 한다.
규칙 찾기
- 불은 상, 하, 좌, 우로 이동할 수 있고 지훈이가 있는 위치로도 이동할 수 있다.
- 지훈이와 불은 동시에 이동하므로, 지훈이는 동일한 시간에 불이 도달하는 위치를 피해가도록 해야한다.
따라서, 불을 먼저 이동하게 한 후, 갱신된 미로 상태에 따라 지훈이의 이동 경로를 설정한다.
✍ 부분 코드 설명
변수 & 클래스 선언
private static char[][] map;
private static Queue<int[]> fire = new ArrayDeque<>();
private static Queue<Person> person = new ArrayDeque<>();
private static int[] dx = new int[]{0, 1, 0, -1};
private static int[] dy = new int[]{1, 0, -1, 0};
public static class Person {
int x, y, count;
public Person(int x, int y, int count) {
this.x = x;
this.y = y;
this.count = count;
}
}
...map: 미로 상태 저장
fire, person 큐: 각각 불의 위치, 지훈이의 위치를 저장
dx, dy: 상, 하, 좌, 우 이동에 사용하는 변수
Person 클래스: 지훈이 위치 및 소요 시간
미로 상태 입력 받기
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int row = Integer.parseInt(st.nextToken());
int col = Integer.parseInt(st.nextToken());
map = new char[row][col];
for (int i = 0; i < row; i++) {
String str = br.readLine();
for (int j = 0; j < str.length(); j++) {
map[i][j] = str.charAt(j);
if (map[i][j] == 'J')
person.offer(new Person(i, j, 1));
else if (map[i][j] == 'F')
fire.offer(new int[]{i, j});
}
}
// bfs 호출
int res = p_bfs();
if(res == -1) System.out.println("IMPOSSIBLE");
else System.out.println(res);
...- 입력한 정보를 바탕으로 map 초기화
- 지훈이의 위치는 한 곳 뿐이므로 위치 및 count는 1로 초기화
- 불의 위치는 fire 큐에 저장
BFS 수행
private static int p_bfs() {
// 지훈이가 이동할 곳이 없을 때까지 반복
while (!person.isEmpty()) {
// 현재 큐에 존재하는 불 개수
int f_len = fire.size();
int i=0;
// 큐에 존재하는 불 개수만큼 반복
while(i<f_len) {
int[] c_fire = fire.poll();
for (int d = 0; d < 4; d++) {
int fx = c_fire[0] + dx[d];
int fy = c_fire[1] + dy[d];
// 불 이동
if (fx >= 0 && fy >= 0 && fx < map.length && fy < map[0].length) {
if (map[fx][fy] == '.') {
map[fx][fy] = 'F'; // 미로 갱신
fire.offer(new int[]{fx, fy}); // 새로운 불의 위치 저장
}
}
}
i++;
}
i=0;
int p_len = person.size();
// 현재 큐에 있는 지훈이 위치 개수 만큼 반복
while(i<p_len) {
Person simon = person.poll();
// 지훈이의 현재 위치가 탈출 가능한 위치인 경우
if(simon.x == 0 || simon.x ==map.length-1 ||
simon.y==0 || simon.y == map[0].length-1)
return simon.count; // 소요시간 반환 및 종료
for (int d = 0; d < 4; d++) {
int px = simon.x + dx[d];
int py = simon.y + dy[d];
if (px >= 0 && py >= 0 && px < map.length && py < map[0].length) {
// 다음 위치가 탈출 가능한 위치인 경우
if (px == 0 || px == map.length - 1 || py == 0 || py == map[0].length) {
if(map[px][py]!='#' && map[px][py]!='F')
return simon.count+1; // 소요시간 반환 및 종료
}
if (map[px][py] == '.') {
map[px][py] = 'J'; // 방문 처리
person.offer(new Person(px, py, simon.count + 1)); // 갱신된 지훈이 위치 저장
}
}
}
i++;
}
}
return -1; // 탈출할 수 없는 경우
}- 앞서 설명한 대로 불 먼저 이동
- 지훈이 이동 시, 현재 지훈이 위치가 탈출 가능한 위치인 경우 소요시간 반환
- 이동 가능한 지훈이 위치 (
px, py)가 탈출 가능한 위치인 경우 소요시간 +1 반환 - 더이상 지훈이가 이동할 위치가 없는 경우, 탈출이 불가능하므로
-1반환
🍳 전체 소스 코드
package Algorithm.BFS;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;
public class N_4179 {
private static char[][] map;
private static Queue<int[]> fire = new ArrayDeque<>();
private static Queue<Person> person = new ArrayDeque<>();
private static int[] dx = new int[]{0, 1, 0, -1};
private static int[] dy = new int[]{1, 0, -1, 0};
public static class Person {
int x, y, count;
public Person(int x, int y, int count) {
this.x = x;
this.y = y;
this.count = count;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int row = Integer.parseInt(st.nextToken());
int col = Integer.parseInt(st.nextToken());
map = new char[row][col];
for (int i = 0; i < row; i++) {
String str = br.readLine();
for (int j = 0; j < str.length(); j++) {
map[i][j] = str.charAt(j);
if (map[i][j] == 'J')
person.offer(new Person(i, j, 1));
else if (map[i][j] == 'F')
fire.offer(new int[]{i, j});
}
}
int res = p_bfs();
if(res == -1) System.out.println("IMPOSSIBLE");
else System.out.println(res);
}
private static int p_bfs() {
while (!person.isEmpty()) {
int f_len = fire.size();
int i=0;
while(i<f_len) {
int[] c_fire = fire.poll();
for (int d = 0; d < 4; d++) {
int fx = c_fire[0] + dx[d];
int fy = c_fire[1] + dy[d];
// 불 이동
if (fx >= 0 && fy >= 0 && fx < map.length && fy < map[0].length) {
if (map[fx][fy] == '.') {
map[fx][fy] = 'F'; // 방문 처리
fire.offer(new int[]{fx, fy}); // 다음 이동
}
}
}
i++;
}
i=0;
int p_len = person.size();
while(i<p_len) {
Person simon = person.poll();
if(simon.x == 0 || simon.x ==map.length-1 ||
simon.y==0 || simon.y == map[0].length-1)
return simon.count;
for (int d = 0; d < 4; d++) {
int px = simon.x + dx[d];
int py = simon.y + dy[d];
if (px >= 0 && py >= 0 && px < map.length && py < map[0].length) {
// 탈출이 가능 지점에 있는 경우
if (px == 0 || px == map.length - 1 || py == 0 || py == map[0].length) {
if(map[px][py]!='#' && map[px][py]!='F')
return simon.count+1;
}
if (map[px][py] == '.') {
map[px][py] = 'J'; // 방문 처리
person.offer(new Person(px, py, simon.count + 1)); // 다음 이동
}
}
}
i++;
}
}
return -1;
}
}
✨ 결과
지훈이가 동시에 이동함을 고려하는 부분에서 오래걸렸다.
동시 라는 조건에 묶여서 p_bfs(지훈 이동), f_bfs(불 이동) 이렇게 두 함수를 작성해서 f_bfs 수행 도중 J를 만나면 p_bfs를 호출하는 로직으로 가볼까 했지만, 더 복잡해지는 것 같았다.
두 번째는 불이 이동하다가, 지훈이를 만나면 IMPOSSIBLE을 뱉도록 할까 했지만, 내 코드에서 방문 처리를 J, F로 했기에 지훈이의 잔상을 만나는 경우가 있어서 취소했다.
마지막으로 현재 불을 먼저 이동시키고, 갱신된 미로 상태에 따라 지훈이를 이동시키도록 했다.
탈출 조건
1. 미로의 초기 상태에서 지훈이의 현 위치가 탈출 가능한 위치인 경우
2. 다음 위치가 탈출 가능한 위치지만#과F가 아닌 경우
이 문제에 투자한 시간은 약 5시간 정도 되는 듯하다.
오래 걸리니 오기로 혼자 풀어보려고 노력했다.
시간 단축은 많이 풀어보는 수밖에 없다. 파이팅!
