[Baekjoon] 4179_불!

Gold IV

문제(출처: https://www.acmicpc.net/problem/4179)

---

<불!>

 

문제 풀이

 

bfs를 활용하여 불을 먼저 이동시킨 후 사람을 이동시킨다.

 

 - my solution (Java)

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 _4179_ { // 불!
	static boolean flag ;
	static char map[][];
	static Queue<int[]> queue, position;
	static int dx[] = { -1, 1, 0, 0 }; // 상하좌우
	static int dy[] = { 0, 0, -1, 1 };
	static int r, c, result;

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());

		r = Integer.parseInt(st.nextToken());
		c = Integer.parseInt(st.nextToken());

		map = new char[r][c];
		queue = new LinkedList<>();

		position = new LinkedList<>();
		flag = false;
		for (int i = 0; i < r; i++) { // input
			String s = bf.readLine();
			for (int j = 0; j < c; j++) {
				map[i][j] = s.charAt(j);
				if (map[i][j] == 'J') {
					position.add(new int[] { i, j, 0 });
				} else if (map[i][j] == 'F') {
					queue.add(new int[] { i, j, 0 });
				}
			}
		}
		result = 0;

		while (true) {
			if (position.size() == 0)
				break;
			result += 1;
			search();
			if (flag)
				break;
		}

		if (flag)
			System.out.println(result);
		else
			System.out.println("IMPOSSIBLE");
	}

	private static void search() {
		while (!queue.isEmpty()) { // fire move
			if(queue.peek()[2]==result-1) {
				int[] temp = queue.poll();
				for (int i = 0; i < 4; i++) {
					int x = temp[0] + dx[i];
					int y = temp[1] + dy[i];
					if (x >= 0 && x < r && y >= 0 && y < c) {
						if (map[x][y] == '.' || map[x][y] == 'J') {
							map[x][y] = 'F';
							queue.add(new int[] { x, y, temp[2] + 1 });
						}
					}
				}
			}else break;
		}
		while (!position.isEmpty() ) { // 지훈 move
			if(position.peek()[2]==result-1) {
				int[] temp = position.poll();
				for (int i = 0; i < 4; i++) {
					int x = temp[0] + dx[i];
					int y = temp[1] + dy[i];
					if (x >= 0 && x < r && y >= 0 && y < c && map[x][y] == '.') {
						position.add(new int[] { x, y, temp[2] + 1 });
						map[x][y]='J';
					} else if (x < 0 || x >= r || y < 0 || y >= c) { // 미로 탈출
						flag = true;
						position.clear();
						break;
					}
				}
				if(flag) break;
			}else break;
		}
	}
}

 

•  Main
  • r, c 입력
  • map : 미로 입력
  • queue, position : 불의 위치와 사람 위치를 [x좌표, y좌표, 이동 횟수] 배열로 저장
  • flag: 종료 조건 (사람이 미로를 탈출한 경우)
  • 미로를 입력 받음과 동시에 사람 위치와 불 위치를 각각 Queue에 저장
  • 무한 반복 : 종료 조건 ) 사람이 미로를 탈출했거나 불이 도달하여 미로를 탈출할 수 없는 경우
  • 사람이 미로를 탈출한 경우 flag가 true이므로 result를 출력 but flag가 false이면 미로를 탈출할 수 없으므로 IMPOSSIBLE 출력
• search
  • 불 이동
    • 1초에 해당하는 불만 이동시키기 위해 queue의 첫 번째 값이 result-1 값과 같다면 첫 번째 값을 뽑아 상하좌우 이동 -> 미로 범위 안이며 지나갈 수 있는 공간 또는 사람의 위치라면 불로 표시 및 queue에 추가 (* 사람의 위치라도 불로 표시하는 이유는 이미 position이라는 queue에 사람의 위치를 저장해두었기 때문에 상관없음)
    • queue의 첫 번째 값이 result-1과 같지 않다면 1초에 해당하는 만큼 불을 다 이동시켰다는 뜻이므로 break
  • 사람 이동
    • 1초에 해당하는 만큼 지훈이를 이동시키기 위해 queue의 첫 번째 값이 result-1 값과 같다면 첫 번째 값을 뽑아 상하좌우 이동 -> 미로 범위 안이며 지나갈 수 있는 공간이라면 queue에 저장 및 map에 표시
    • 상하좌우 이동시 미로 범위 밖이라면 미로 탈출이라는 뜻이므로 flag를 true로 바꾼 후 break
    • queue의 첫 번째 값이 result-1 값과 같지 않으면 1초에 해당하는 만큼 사람이 이동했다는 뜻이므로 break

---

생각🤔

 

처음에 시간 초과가 발생한 이유는 매번 계속해서 반복문을 사용하여 불의 위치와 사람의 위치를 각 queue에 넣어주는 작업을 했기 때문이었다. 이 부분을 바꾸니 이번에는 메모리 초과가 발생하였다. 이 부분은 사람이 이동할 때 map을 지나갈 수 있는 공간으로 다시 바꿔줌으로써 동작이 중복되어 메모리 초과가 발생하는 것이라 생각하였다. 이 부분을 고치고 조건을 조금 더 고치니 통과할 수 있었다.

 

---