문제
상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다.
매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에는 불이 붙지 않는다. 상근이는 동서남북 인접한 칸으로 이동할 수 있으며, 1초가 걸린다. 상근이는 벽을 통과할 수 없고, 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. 상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다.
빌딩의 지도가 주어졌을 때, 얼마나 빨리 빌딩을 탈출할 수 있는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 최대 100개이다.
각 테스트 케이스의 첫째 줄에는 빌딩 지도의 너비와 높이 w와 h가 주어진다. (1 ≤ w,h ≤ 1000)
다음 h개 줄에는 w개의 문자, 빌딩의 지도가 주어진다.
'.': 빈 공간
'#': 벽
'@': 상근이의 시작 위치
'*': 불
각 지도에 @의 개수는 하나이다.
출력
각 테스트 케이스마다 빌딩을 탈출하는데 가장 빠른 시간을 출력한다. 빌딩을 탈출할 수 없는 경우에는 "IMPOSSIBLE"을 출력한다.
풀이
불에 대해 bfs 탐색을 한 후, 상근이에 대해 bfs 탐색을 하는데, 상근이가 bfs 탐색할 때, 불이 거치지 않았거나, 불의 탐색(이동) 횟수보다 더 작은 경우 이동하도록 처리한다. 이후 상근이의 탐색 과정에서 좌표가 빌딩 밖으로 나가는 경우 해당 이동 카운트 횟수를 출력한다. 만약에 빌딩밖으로 나가지 못한다면(큐가 빈채로 그냥 끝난다면) "IMPOSSIBLE" 을 출력한다.
(실패) 첫번째 풀이
각각의 불에 대해 BFS 탐색을 하되, 방문 누적 순서 배열에서 각 칸마다 불이 도달할때까지 최소 거리를 계산했어야 했는데, 불이 탐색했던 칸은 최소 걸린 시간을 계산하지 않고 모두 PASS 해버려서 실패했다. 그리고 방문 배열 초기값을 0으로 설정하니, 불의 초기 위치도 방문 배열에서 0으로 기록되기에 헷갈리게 된다.
따라서 아래와 같은 불상사가 발생한다
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.StringTokenizer;
class Node{
int row;
int col;
int cnt;
public Node(int row, int col, int cnt) {
this.row = row;
this.col = col;
this.cnt = cnt;
}
}
public class Main {
static int t;
static int w;
static int h;
static char[][] map;
static int[][] fire_visited;
static int[][] sang_visited;
static ArrayDeque<Node> nodes;
static int ans;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
t = Integer.parseInt(br.readLine());
for(int tc = 0; tc < t; tc++) {
StringTokenizer st = new StringTokenizer(br.readLine());
w = Integer.parseInt(st.nextToken());
h = Integer.parseInt(st.nextToken());
map = new char[h][w];
fire_visited = new int[h][w];
sang_visited = new int[h][w];
ans = 0;
// map 배열 입력 받기
for(int i = 0; i < h; i++) {
String s = br.readLine();
for(int j = 0; j < w; j++) {
map[i][j] = s.charAt(j);
}
}
// 불에 대해 탐색
for(int i = 0; i < h; i++) {
for(int j = 0; j < w; j++) {
if(map[i][j] == '*') {
fire_bfs(i,j);
}
}
}
// printArr(fire_visited);
// 상근이에 대해 탐색
// 탈출하면 시간 출력 후 종료
for(int i = 0; i < h; i++) {
for(int j = 0; j < w; j++) {
if(map[i][j] == '@') {
sang_bfs(i,j);
}
}
}
// printArr(sang_visited);
// 정답 출력
if(ans != 0) {
System.out.println(ans);
}
else System.out.println("IMPOSSIBLE");
}
}
static int[] dRow = {-1,0,1,0};
static int[] dCol = {0,1,0,-1};
static void fire_bfs(int row, int col) {
nodes = new ArrayDeque<>();
fire_visited[row][col] = 0;
nodes.offer(new Node(row,col,0));
while(!nodes.isEmpty()) {
Node n = nodes.poll();
// 4방면으로 확인
for(int d = 0; d < 4; d++) {
int nr = n.row + dRow[d];
int nc = n.col + dCol[d];
if(fire_Possible(nr, nc)) {
fire_visited[nr][nc] = n.cnt+1;
nodes.offer(new Node(nr, nc, n.cnt+1));
}
}
}
}
static void sang_bfs(int row, int col) {
nodes = new ArrayDeque<>();
sang_visited[row][col] = 0;
nodes.offer(new Node(row, col, 0));
while(!nodes.isEmpty()) {
Node n = nodes.poll();
// nodes에 넣는건 무조건 정상임 4방 탐색시에 범위 아웃 검사해야함
// 4방 탐색
for(int i = 0; i < 4; i++) {
int nr = n.row + dRow[i];
int nc = n.col + dCol[i];
if(isOut(nr,nc)) {
ans = n.cnt+1;
return;
}
if(sang_Possible(nr,nc, n.cnt)) {
sang_visited[nr][nc] = n.cnt + 1;
nodes.offer(new Node(nr,nc,n.cnt+1));
}
}
}
}
static boolean sang_Possible(int row, int col, int cnt) {
// 정상 범위 내면서 벽이아니고
// 방문하지 않았고, 불이 지나가는 번째보다 빠른 경우
if(row >= 0 && row < h && col >= 0 && col < w && map[row][col] == '.'
&& sang_visited[row][col] == 0 && (fire_visited[row][col] == 0 || fire_visited[row][col]> cnt+1)) {
return true;
}
return false;
}
static boolean fire_Possible(int row, int col) {
// 정상 범위 내면서 벽,불이 아니고
// 방문하지 않은 경우
if(row >= 0 && row < h && col >= 0 && col < w && map[row][col] != '#'
&& map[row][col] != '*' && fire_visited[row][col] == 0) {
return true;
}
return false;
}
static void printArr(int[][] arr) {
for(int i = 0; i < h; i++) {
for(int j = 0; j < w; j++) {
System.out.print(arr[i][j] + " ");
}
System.out.println();
}
}
static boolean isOut(int row, int col) {
return row < 0 || row >= h || col < 0 || col >= w;
}
}(실패) 두번째 풀이
첫번째 풀이의 잘못된 점을 보완하기 위해, 방문 배열의 초기값을 -1로 설정했다. 그리고 각 불에 BFS 탐색을 하되, 불이 번지지 않았거나, 불이 번졌어도 현재의 BFS 탐색을 시작한 불이 더 빠르게 번지는 경우 값을 재설정하는 과정을 거쳤다.
그러나 시간 초과가 발생했다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.StringTokenizer;
class Node{
int row;
int col;
int cnt;
public Node(int row, int col, int cnt) {
this.row = row;
this.col = col;
this.cnt = cnt;
}
}
public class Main {
static int t;
static int w;
static int h;
static char[][] map;
static int[][] fire_visited;
static int[][] sang_visited;
static ArrayDeque<Node> nodes;
static int ans;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
t = Integer.parseInt(br.readLine());
for(int tc = 0; tc < t; tc++) {
StringTokenizer st = new StringTokenizer(br.readLine());
w = Integer.parseInt(st.nextToken());
h = Integer.parseInt(st.nextToken());
map = new char[h][w];
fire_visited = new int[h][w];
sang_visited = new int[h][w];
ans = 0;
// 방문 배열 초기화
for(int i = 0; i < h; i++) {
Arrays.fill(fire_visited[i], -1);
Arrays.fill(sang_visited[i], -1);
}
// map 배열 입력 받기
for(int i = 0; i < h; i++) {
String s = br.readLine();
for(int j = 0; j < w; j++) {
map[i][j] = s.charAt(j);
}
}
// 불에 대해 탐색
for(int i = 0; i < h; i++) {
for(int j = 0; j < w; j++) {
if(map[i][j] == '*') {
fire_bfs(i,j);
}
}
}
// 상근이에 대해 탐색
// 탈출하면 시간 출력 후 종료
for(int i = 0; i < h; i++) {
for(int j = 0; j < w; j++) {
if(map[i][j] == '@') {
sang_bfs(i,j);
}
}
}
// 정답 출력
if(ans != 0) {
System.out.println(ans);
}
else System.out.println("IMPOSSIBLE");
}
}
static int[] dRow = {-1,0,1,0};
static int[] dCol = {0,1,0,-1};
static void fire_bfs(int row, int col) {
nodes = new ArrayDeque<>();
fire_visited[row][col] = 0;
nodes.offer(new Node(row,col,0));
while(!nodes.isEmpty()) {
Node n = nodes.poll();
// 4방면으로 확인
for(int d = 0; d < 4; d++) {
int nr = n.row + dRow[d];
int nc = n.col + dCol[d];
if(fire_Possible(nr, nc, n.cnt)) {
fire_visited[nr][nc] = n.cnt+1;
nodes.offer(new Node(nr, nc, n.cnt+1));
}
}
}
}
static void sang_bfs(int row, int col) {
nodes = new ArrayDeque<>();
sang_visited[row][col] = 0;
nodes.offer(new Node(row, col, 0));
while(!nodes.isEmpty()) {
Node n = nodes.poll();
// nodes에 넣는건 무조건 정상임 4방 탐색시에 범위 아웃 검사해야함
// 4방 탐색
for(int i = 0; i < 4; i++) {
int nr = n.row + dRow[i];
int nc = n.col + dCol[i];
if(isOut(nr,nc)) {
ans = n.cnt+1;
return;
}
if(sang_Possible(nr,nc, n.cnt)) {
sang_visited[nr][nc] = n.cnt + 1;
nodes.offer(new Node(nr,nc,n.cnt+1));
}
}
}
}
static boolean sang_Possible(int row, int col, int cnt) {
// 정상 범위 내면서 벽이아니고
// 방문하지 않았고, 불이 지나가는 번째보다 빠른 경우
if(row >= 0 && row < h && col >= 0 && col < w && map[row][col] == '.'
&& sang_visited[row][col] == -1 && (fire_visited[row][col] == -1 || fire_visited[row][col]> cnt+1)) {
return true;
}
return false;
}
static boolean fire_Possible(int row, int col, int cnt) {
// 정상 범위 내면서 벽,불이 아니고
// 방문하지 않은 경우
if(row >= 0 && row < h && col >= 0 && col < w && map[row][col] != '#'
&& (fire_visited[row][col] == -1 || fire_visited[row][col] > cnt+1)) {
return true;
}
return false;
}
static boolean isOut(int row, int col) {
return row < 0 || row >= h || col < 0 || col >= w;
}
}(성공) 세번째 풀이
불의 좌표를 모두 큐에 넣고 한번의 BFS 함수 호출로 모든 불의 번짐 계산을 처리했다.
이를 통해 시간 초과를 해결할 수 있었다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.StringTokenizer;
class Node{
int row;
int col;
int cnt;
public Node(int row, int col, int cnt) {
this.row = row;
this.col = col;
this.cnt = cnt;
}
}
public class Main {
static int t;
static int w;
static int h;
static char[][] map;
static int[][] fire_visited;
static int[][] sang_visited;
static ArrayDeque<Node> nodes;
static int ans;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
t = Integer.parseInt(br.readLine());
for(int tc = 0; tc < t; tc++) {
StringTokenizer st = new StringTokenizer(br.readLine());
w = Integer.parseInt(st.nextToken());
h = Integer.parseInt(st.nextToken());
map = new char[h][w];
fire_visited = new int[h][w];
sang_visited = new int[h][w];
ans = 0;
// 방문 배열 초기화
for(int i = 0; i < h; i++) {
Arrays.fill(fire_visited[i], -1);
Arrays.fill(sang_visited[i], -1);
}
// map 배열 입력 받기
for(int i = 0; i < h; i++) {
String s = br.readLine();
for(int j = 0; j < w; j++) {
map[i][j] = s.charAt(j);
}
}
// 불에 대해 탐색
nodes = new ArrayDeque<>();
for(int i = 0; i < h; i++) {
for(int j = 0; j < w; j++) {
if(map[i][j] == '*') {
nodes.offer(new Node(i,j,0));
fire_visited[i][j] = 0;
}
}
}
fire_bfs();
// 상근이에 대해 탐색
// 탈출하면 시간 출력 후 종료
for(int i = 0; i < h; i++) {
for(int j = 0; j < w; j++) {
if(map[i][j] == '@') {
sang_bfs(i,j);
}
}
}
// 정답 출력
if(ans != 0) {
System.out.println(ans);
}
else System.out.println("IMPOSSIBLE");
}
}
static int[] dRow = {-1,0,1,0};
static int[] dCol = {0,1,0,-1};
static void fire_bfs() {
while(!nodes.isEmpty()) {
Node n = nodes.poll();
// 4방면으로 확인
for(int d = 0; d < 4; d++) {
int nr = n.row + dRow[d];
int nc = n.col + dCol[d];
if(fire_Possible(nr, nc, n.cnt)) {
fire_visited[nr][nc] = n.cnt+1;
nodes.offer(new Node(nr, nc, n.cnt+1));
}
}
}
}
static void sang_bfs(int row, int col) {
nodes = new ArrayDeque<>();
sang_visited[row][col] = 0;
nodes.offer(new Node(row, col, 0));
while(!nodes.isEmpty()) {
Node n = nodes.poll();
// nodes에 넣는건 무조건 정상임 4방 탐색시에 범위 아웃 검사해야함
// 4방 탐색
for(int i = 0; i < 4; i++) {
int nr = n.row + dRow[i];
int nc = n.col + dCol[i];
if(isOut(nr,nc)) {
ans = n.cnt+1;
return;
}
if(sang_Possible(nr,nc, n.cnt)) {
sang_visited[nr][nc] = n.cnt + 1;
nodes.offer(new Node(nr,nc,n.cnt+1));
}
}
}
}
static boolean sang_Possible(int row, int col, int cnt) {
// 정상 범위 내면서 벽이아니고
// 방문하지 않았고, 불이 지나가는 번째보다 빠른 경우
if(row >= 0 && row < h && col >= 0 && col < w && map[row][col] == '.'
&& sang_visited[row][col] == -1 && (fire_visited[row][col] == -1 || fire_visited[row][col]> cnt+1)) {
return true;
}
return false;
}
static boolean fire_Possible(int row, int col, int cnt) {
// 정상 범위 내면서 벽,불이 아니고
// 방문하지 않은 경우
if(row >= 0 && row < h && col >= 0 && col < w && map[row][col] != '#'
&& (fire_visited[row][col] == -1 || fire_visited[row][col] > cnt+1)) {
return true;
}
return false;
}
static boolean isOut(int row, int col) {
return row < 0 || row >= h || col < 0 || col >= w;
}
}
better than yesterday