불(BJ_G4_5427)

1. 문제 링크

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

5427번: 불

---

 

2. 나의 코드

메모리: 116604kb
시간: 924ms
코드 길이: 2228B
시간 복잡도 : O(RC)
설명
- 사람이 이동하는 경로와 불이 번지는 경로를 따로 큐로 처리
- 만약 더이상 사람이 이동할 경로가 없으면 Impossible 출력
- 만약 사람이 map의 가장자리에 도착하면 시간을 출력

import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	
	static int[] dr = {-1, 1, 0, 0};
	static int[] dc = {0, 0, -1, 1};
	static int R, C;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		int test = Integer.parseInt(br.readLine());
		for (int t = 0; t < test; t++) {
			Queue<Point> fires = new LinkedList<>();
			Queue<Point> humans = new LinkedList<>();
			int result = 0;
			boolean possible = false;
			st = new StringTokenizer(br.readLine());
			C = Integer.parseInt(st.nextToken());
			R = Integer.parseInt(st.nextToken());
			char[][] map = new char[R][C];
			for (int i = 0; i < R; i++) {
				String s = br.readLine();
				for (int j = 0; j < C; j++) {
					map[i][j] = s.charAt(j);
					if (map[i][j] == '*') fires.offer(new Point(i, j));
					else if (map[i][j] == '@') humans.offer(new Point(i, j));
				}
			}
			while (!possible && !humans.isEmpty()) {
				result++;
				// 불 번지기
				for (int i = 0, size = fires.size(); i < size; i++) {
					Point fireNow = fires.poll();
					for (int d = 0; d < 4; d++) {
						int nr = fireNow.x + dr[d];
						int nc = fireNow.y + dc[d];
						
						if (isValid(nr, nc) && map[nr][nc] != '#' && map[nr][nc] != '*') {
							map[nr][nc] = '*';
							fires.offer(new Point(nr, nc));
						}
					}
				}
				// 사람 이동
				for (int i = 0, size = humans.size(); i < size; i++) {
					Point humanNow = humans.poll();
					if (humanNow.x == 0 || humanNow.x == R - 1 || humanNow.y == 0 || humanNow.y == C - 1) {
						possible = true;
						break;
					}
					for (int d = 0; d < 4; d++) {
						int nr = humanNow.x + dr[d];
						int nc = humanNow.y + dc[d];
						
						if (isValid(nr, nc) && map[nr][nc] == '.') {
							map[nr][nc] = '@';
							humans.offer(new Point(nr, nc));
						}
					}
				}
			}
			System.out.println((possible) ? result : "IMPOSSIBLE");
		}
	}
	
	public static boolean isValid(int r, int c) {
		return 0 <= r && r < R && 0 <= c && c < C;
	}
}

 

---

 

3. 정답 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int w,h;
	static char[][] map;
	static Queue<int[]> person;
	static Queue<int[]> fire;
	static int[] dx = {-1,1,0,0};
	static int[] dy = {0,0,-1,1};
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int tc = Integer.parseInt(br.readLine());
		
		StringBuilder sb = new StringBuilder();
		while(tc-->0) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			w = Integer.parseInt(st.nextToken());
			h = Integer.parseInt(st.nextToken());
			
			map = new char[h][w];
			fire = new LinkedList<>();
			person = new LinkedList<>();
			for(int i=0; i<h; i++) {
				String line = br.readLine();
				for(int j=0; j<w; j++) {
					char c = line.charAt(j);
					if(c=='@') {
						person.add(new int[] {j,i,0});
					}else if(c=='*') {
						fire.add(new int[] {j,i});
					}
					map[i][j] = c;
				}
			}
			int res= -1;
			out : while(true) {
				// 1. 불 번짐
				int fSize = fire.size();
				for(int i=0; i<fSize; i++) {
					int[] pos = fire.poll();
					int px = pos[0], py = pos[1];
					fireMarking(px, py);
				}
				
				// 2. 상근 이동 (1번 불번짐 영향 x, 그러나 번질 곳으로 이동은 x)
				int pSize = person.size();
				for(int i=0; i<pSize; i++) {
					int[] pos = person.poll();
					int px = pos[0], py = pos[1], time =pos[2];
					res = escape(px, py, time);
					if(res != -1) {
						break out;
					}
				}
				if(person.isEmpty()) break;
			}
			
			if(res !=-1) sb.append(res+"\n");
			else sb.append("IMPOSSIBLE\n");
		}
		System.out.println(sb.toString());
	
	}
	
	static int escape(int x, int y, int time) {
		for(int i=0; i<4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			
			if(nx<0 || nx>w-1 || ny<0 || ny>h-1) {
				return time+1;
			}
			
			if(map[ny][nx] == '.') {
				map[ny][nx] = '@';
				person.add(new int[] {nx, ny, time+1});
			}
		}
		return -1;
		
	}
	
	static void fireMarking(int x, int y) {
		for(int i=0; i<4; i++) {
			int nx = x+dx[i];
			int ny = y+dy[i];
			
			if(nx<0 || nx>w-1 || ny<0 || ny>h-1) continue;
			
			// 빈공간 , 상근 위치 
			if(map[ny][nx] == '.' || map[ny][nx] == '@') {
				map[ny][nx] = '*';
				fire.add(new int[] {nx,ny});
			}
		}
	}
}

 

---

 

4. 배운 점

- 만약 큐의 사이즈 만큼 돌려야 한다면 size를 선언한 후 하도록 하자