문제 링크
문제
상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다.
매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에는 불이 붙지 않는다. 상근이는 동서남북 인접한 칸으로 이동할 수 있으며, 1초가 걸린다. 상근이는 벽을 통과할 수 없고, 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. 상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다.
빌딩의 지도가 주어졌을 때, 얼마나 빨리 빌딩을 탈출할 수 있는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 최대 100개이다.
각 테스트 케이스의 첫째 줄에는 빌딩 지도의 너비와 높이 w와 h가 주어진다. (1 ≤ w,h ≤ 1000)
다음 h개 줄에는 w개의 문자, 빌딩의 지도가 주어진다.
- '.': 빈 공간
- '#': 벽
- '@': 상근이의 시작 위치
- '*': 불
각 지도에 @의 개수는 하나이다.
출력
각 테스트 케이스마다 빌딩을 탈출하는데 가장 빠른 시간을 출력한다. 빌딩을 탈출할 수 없는 경우에는 "IMPOSSIBLE"을 출력한다.
문제 해석
문제의 조건을 나열하면 다음과 같다.
- 주어진 객체는 벽, 불, 상근이 3개이다.
- 움직이는 객체는 불과 상근이이다.
- 모든 움직이는 객체는 빈칸으로 동서남북으로 1칸씩 움직일 수 있다.
- 움직일때 걸리는 시간은 1초이다.
- 이때 불은 상근이가 있는 공간에도 이동할 수 있다.
- 이 경우에 상근이가 있는 칸에 불이 와도 상근이는 다른 칸으로 이동할 수 있다.
- 상근이가 빌당 밖으로 벗어나면 상근이는 빌딩을 탈출한 것으로 판단한다.
- 빌딩을 탈출한 시간 중 최소 시간을 출력한다.
- 만약 벗어나지 못하면 상근이는 빌딩을 탈출하지 못한것으로 판단한다.
- 탈출 시간은 없으므로 IMPOSSIBLE를 출력한다.
- 높이와 너비는 최소 1이상 1,000이하이다.
우선 문제를 푸는 가장 쉬운 방법이면서 이해도 높일 수 있도록 시뮬레이션을 진행해보자.
시뮬레이션을 진행할 때 주의점 2가지
1. 최소시간
상근이를 1초씩 움직였을 때 가장 먼저 탈출한 경우가 최소시간이므로 더이상 최소시간을 위해 탐색할 필요가 없다.
2. 이동우선권(불 VS 사람)
이 문제는 불과 사람이 1초에 동시에 이동한다. 하지만 코드 상 동시에 움직일 수 없으므로 불을 먼저 움직일지 상근이를 먼저 움직일지 선택해야한다.
어떤 것을 움직여도 상관 없을 것 처럼 보이지만 불을 먼저 움직여야한다. 왜냐하면 상근의 움직임은 불에 영향을 끼치지 못하지만 불의 움직임은 상근이의 움직임에 영향을 끼치기 때문이다.
상근이가 이동할 수 있는 곳은 빈칸 뿐이다. 하지만 불은 빈칸과 상근이가 있는 곳에 움직일 수 있다. 그러므로 불을 먼저 움직이면 상근이의 움직임이 제한이 걸리므로 상근이의 움직임을 최소화할 수 있어 상근이가 가지 못하는 불의 위치에 움직이는 경우를 막을 수 있다. 또한 아직 상근이가 움직이지 않았으면 불과 상근이는 같은 위치에 존재할 수 있다는 조건이 있므로 불을 먼저 움직이는 것이 코드로 구현하는데 더 편할 것이다.
상근이를 먼저 움직여도 된다!
물론 로직에 따라 상근이를 먼저 움직여도 되는 경우가 있다. 예를 들어 상근이를 움직이고 불을 움직인 뒤 불에 타지 않은 상근이만 찾아내서 다음 움직임을 하는 로직이라면 상관이 없을 것이다.하지만 이렇게 된다면 움직일 수 있는 상근이를 찾아야하기 때문에 해당 로직을 추가함에 따라서 생기는 예외케이스가 등장하게 되므로 예외케이스를 최대한 줄이기 위해 상근이를 먼저 움직이는 로직은 안하는 것을 추천한다. 에외케이스를 줄이기 위해선 분기,조건 검증 테스트의 원리에 따라 조건문을 줄이는 것이 예외 케이스를 줄이기 가장 좋기 때문에 상근이를 먼저 움직이는 경우는 추천하지 않는다.
시뮬레이션
주어진 예시 중 2번째 테스트 케이스의 시뮬레이션 모습은 다음과 같다.
최종적으로 상근이는 최초로 5초에 빌딩에서 벗어나므로 최소 시간은 5초인 것을 시뮬레이션을 통해 알 수 있다. 이제 시뮬레이션으로 구현하면 제한된 시간인 1초이내에 풀 수 있는지 시간복잡도를 계산해보자.
시간복잡도 = O(N^2)
건물의 높이, 너비의 크기는 각각 최대 1,000이므로 각 공간의 개수는 최대 1,000 X1,000 = 1,000,000이다.
이때 불이 이동할 수 있는 모든 경우의 수는 모든 공간에 가는 것이므로 최대 1,000,000개이고 상근이가 이동할 수 있는 경우의 수도 최대 1,000,000개이다. 1,000,000은 1억보다 작으므로 주어진 시간인 1초 이내에 모두 탐색이 가능하다. 그러므로 모든 경우의 수를 탐색하면 탈출최소시간을 1초 이내로 구할 수 있다.
사용 알고리즘 : BFS
경우의 수를 탐색하는 방법은 크게 BFS와 DFS가 있는데 DFS는 재귀 메소드 콜로 인해 연산 시간과 메모리를 추가적으로 사용하므로 BFS를 이용해 문제를 풀이했다.
코드
import java.io.*;
import java.util.*;
public class Main {
final static char EMPTY = '.'; //변하지 않는 상수값이므로 final을 설정
final static char WALL = '#';
final static char PEOPLE = '@';
final static char FIRE = '*';
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader((System.in)));
int T = Integer.parseInt(br.readLine());
for(int testCase = 1; testCase<=T; testCase++){
String input = br.readLine();
String[] splitInput = input.split(" ");
int w = Integer.parseInt(splitInput[0]);
int h = Integer.parseInt(splitInput[1]);
char[][] buildingMap = new char[h][w];
//BFS를 위한 큐 준비
Queue<Coordinate> peopleQ = new LinkedList<>(); //이동가능한 상근이의 좌표값
Queue<Coordinate> fireQ = new LinkedList<>(); //이동가능한 불의 좌표값
//입력값으로 시뮬레이션을 위한 빌딩의 모습을 2차원 배열로 저장
for(int i=0;i<h;i++){
input = br.readLine();
for(int j=0;j<input.length();j++){
buildingMap[i][j] = input.charAt(j);
if(buildingMap[i][j] == PEOPLE){
peopleQ.add(new Coordinate(i,j));
}
else if(buildingMap[i][j] == FIRE){
fireQ.add(new Coordinate(i,j));
}
}
}
int[]dx = {-1,1,0,0}; //동서남북 이동 벡터
int[]dy = {0,0,-1,1};
int time = 0; //탈출 최소 시간
boolean find = false; //탈출할 방법 있음 변수
//이동할 상근이가 있는 경우 탈출할 방법 탐색
while(!peopleQ.isEmpty()){
Queue<Coordinate> nextFireQ = new LinkedList<>(); //다음 이동 가능한 불 좌표 큐
//모든 불 탐색
while(!fireQ.isEmpty()){
Coordinate fire = fireQ.poll();
//4방향 탐색
for(int i=0;i<dx.length;i++){
Coordinate nextFire = new Coordinate(fire.row + dx[i],fire.col+ dy[i]);
//맵 밖으로 나가는 경우
if(outOfArray(nextFire,buildingMap)){
continue;
}
if(buildingMap[nextFire.row][nextFire.col] == WALL){
continue;
}
if(buildingMap[nextFire.row][nextFire.col] == FIRE){
continue;
}
//해당 좌표값을 불로 변경하여 방문처리
buildingMap[nextFire.row][nextFire.col] = FIRE;
nextFireQ.add(nextFire);
}
}
fireQ = nextFireQ;
Queue<Coordinate> nextPeopleQ = new LinkedList<>();
//모든 상근이의 위치 탐색
while(!peopleQ.isEmpty()){
Coordinate people = peopleQ.poll();
//맵의 가장자리에 위치하면 탈출이 가능하므로 탐색 종료
if(canEscape(people,buildingMap)){
find = true;
break;
}
for(int i=0;i<dx.length;i++){
Coordinate nextPeople = new Coordinate(people.row + dx[i],people.col+ dy[i]);
if(outOfArray(nextPeople,buildingMap)){
continue;
}
if(buildingMap[nextPeople.row][nextPeople.col] != EMPTY){
continue;
}
buildingMap[nextPeople.row][nextPeople.col] = PEOPLE;
nextPeopleQ.add(nextPeople);
}
}
peopleQ = nextPeopleQ;
if(find){
time++; //해당 시간은 가장자로 가는 시간이므로 맵밖으로 나가는 시간을 더해야한다.
break;
}
time++; //1초가 지남
}
String result = find ? String.valueOf(time) : "IMPOSSIBLE";
System.out.println(result);
}
}
//배열 밖으로 나가는지 확인하는 메소드
public static boolean outOfArray(Coordinate coordinate, char[][] map){
if(coordinate.row < 0 || coordinate.col < 0 || coordinate.row >= map.length || coordinate.col >=map[0].length){
return true;
}
return false;
}
//탈출할 수 있는지(가장자리인지) 확인하는 메소드
public static boolean canEscape(Coordinate coordinate, char[][] map){
if(coordinate.row == 0 || coordinate.col == 0 || coordinate.row == map.length-1 || coordinate.col == map[0].length-1){
return true;
}
return false;
}
}
//좌표 객체
class Coordinate{
int row;
int col;
public Coordinate(){}
public Coordinate(int row, int col){
this.row = row;
this.col = col;
}
}
실행 결과
키워드
- 동서남북
- 4방향 벡터이므로 BFS을 이용한 탐색일 가능성을 가지고 있다
- 최소 시간
- 최대한 빨리 구하는 방법을 구하는 것으로 크게 그리디, DP, 브루트 포스, 그래프 탐색 4가지 가능성을 가지고 있다
팁
1. 동시에 움직이는 것이 있다면 다른 객체의 움직임에 영향을 끼치는 객체부터 판단한다.
2. 동서남북으로 이동이라는 말과 N이 적당히 작다면(1,000이하) 시뮬레이션, bfs문제인 경우가 많으므로 구현부터 따져본다.
3. 예외케이스를 적게 만들려면 분기(조건문)를 적게 만들어야 한다.
'알고리즘 문제 풀이 > 해설' 카테고리의 다른 글
| [백준 14226][Gold 4] - 이모티콘 (JAVA) (2) | 2024.02.07 |
|---|---|
| [백준 1700][Gold 1] - 멀티탭 스케줄링(JAVA) (0) | 2024.02.05 |
| [백준 1914][Silver 1] - 하노이 탑(JAVA) (0) | 2024.02.04 |
| [백준 15988][Silver 2] - 1, 2, 3 더하기 3(JAVA) (0) | 2024.02.03 |
| [백준 1744][Gold 4] - 수 묶기(JAVA) (0) | 2024.02.02 |