[BJ] 5427 : 불

       문제 요약        

- 문제

https://www.acmicpc.net/problem/5427

 

 

 

- 입출력

출력 : 빌딩을 탈출하는데 가장 빠른 시간

 

         아이디어        

 

이동하는 주체가 불 / 상근 둘이다

 

불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 움직일 수 없다고 했으므로 

불 이동하고 상근이가 이동할 수 있는 곳으로 이동하면 된다고 생각했다

 

그리고, 불이 상하좌우로 한번 이동, 상근이가 상하좌우로 한번 이동, 하는 과정이 

하나의 시간 내에 움직이므로

BFS를 거리 별로 끊어야 한다고 생각했다 

 

[방안1] while (true) { bfs bfs } 

대략적인 알고리즘은

1. 불 이동 (단, 벽 X + 이미 불이 난 곳은 상근이가 이동할 수 없도록 표시했으므로 고려하지 않기)

2. 상근 이동 (단, EMPTY. 만약 상근이가 다음 갈 곳이 h * w 밖이면 탈출)

만약에 상근이가 이동할 위치가 없는데 탈출에 성공하지 못했다면 탈출이 불가능한 경우이다 

 

처음에 h * w 를 바꿔 작성해서 index out of range exception이 났고

두번째에는 메모리 초과가 났다

왜 메모리 초과가 났을까 생각해봤더니 

불의 이동은 불 이동했다 표시하고 그 부분으로는 안 번지니까 경우의 수가 줄어드는데

상근이 이동은 방문했던 곳을 다시 방문하는 경우를 고려하지 않고 있었다 

그래서 상근이 방문 여부를 확인할 수 있는 vistied 배열을 추가하였다

 

[방안2] 

나중에 생각해보니 1) 불이 언제 이후로 계속 나 있는 상태다 2) 불이 아에 안날 곳이다 를 표시해두고

상근이가 시간에 따라 움직이는 방법도 있겠다 싶었다

근데 1) 다 돌고 2) 도는 거라 걍 방안 1 함

 

         소스코드        

[방안1] 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main { //16637
  static int testCase;
  static char[][] box;
  static char START = '@', WALL = '#', EMPTY = '.', FIRE='*';
    public static void main(String[] args) throws Exception{
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      testCase = Integer.parseInt(br.readLine());
      for (int t = 0; t < testCase; t++) {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int w = Integer.parseInt(st.nextToken());
        int h = Integer.parseInt(st.nextToken());
        boolean[][] sangunVisited = new boolean[h][w];

        Queue<int[]> sangun = new ArrayDeque<>();
        Queue<int[]> fires = new ArrayDeque<>();
        box = new char[h][w];
        for (int i = 0; i < h; i++) {
          String line = br.readLine();
          for (int j = 0; j < w; j++) {
            box[i][j] = line.charAt(j);
            if (box[i][j] == START) {
            	sangun.add(new int[] {i, j});
            	sangunVisited[i][j] = true;
            } else if (box[i][j] == FIRE) {
            	fires.add(new int[] {i, j});
            }
          }
        }
        
        // 1) 불 이동 : 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 움직일 수 없음
        // 2) 상근이 이동 
        int[][] way = {{-1,0}, {1,0}, {0,-1}, {0,1}};
       
        boolean isExit = false;
        int exitTime = 1;
        while(true) {
            // 불 이동
            Queue<int[]> newFires = new ArrayDeque<>();
            while(!fires.isEmpty()) {
            	int[] now = fires.poll();
            	
            	for(int wi = 0; wi < 4; wi++) {
            		int nx = now[0] + way[wi][0];
            		int ny = now[1] + way[wi][1];
            		if(nx < 0 || nx >= h || ny < 0 || ny >= w) {
            			continue;
            		}
            		if(box[nx][ny] == WALL || box[nx][ny] == FIRE) {
            			continue;
            		}
            		box[nx][ny] = FIRE;
            		newFires.add(new int[] {nx, ny});
            	}	
            }
            
            // 상근이 이동
            Queue<int[]> nextSangun = new ArrayDeque<>();
            
            while(!sangun.isEmpty()) {
            	int[] now = sangun.poll();
            	
                for (int wi = 0; wi < 4; wi ++) {
                	int nx = now[0] + way[wi][0];
                	int ny = now[1] + way[wi][1];
                	if(nx < 0 || nx >= h || ny < 0 || ny >= w) {isExit = true; break;}
                	if(sangunVisited[nx][ny])continue;
                	if (box[nx][ny] == EMPTY) {
                    	nextSangun.add(new int[] {nx, ny});  
                    	sangunVisited[nx][ny] = true;
                	}
                }
            }
            if(isExit) { // 성공 조건
            	break;
            }
         
            if (nextSangun.isEmpty()) { // 탈출 불가능
            	break;
            }
            
            // 다음 가능한 상근이 위치
            sangun = nextSangun;
            // 다음불
            fires = newFires;
            exitTime++;
        }
        
        if(isExit) {
        	System.out.println(exitTime);
        } else {
        	System.out.println("IMPOSSIBLE");
        }
      }
    }

}