[너비우선탐색] 백준 5427번 불 - JAVA

 

BFS DFS가 좀 익숙해졌으니

언젠가 태영이 오빠가 추천해준 '불'이라는 문제를 풀어보겠다.

 

불! 이라는 문제도 있는 거 같은데,

이 문제가 더 까다로운 모양이다.

 

 

---

1. 문제출처

---

 

5427번: 불

 

 

갖은 고난을 맞이하여 겨우 풀어 낸 문제 ... Let's GO!

 

 

---

2. 설계

---

 

1) 실패한 설계

그렇다... 처음에는 각각 깊이를 파고들어 1 경로씩 탐색하고자 DFS로 접근했었다...

근데 문제가 있었으니... 바로 배열을  주고 받을 때 같은 시간 대 별로 같은 배열을 공유하지 못한다는 점이다.

예를들어 2초에 갈 수 있는 거리들을 체크해주고자 할 때 재귀를 도는데, 3초, 4초 ... 끝까지 다 체크해주고,

다시 돌아와도 2초에 있던 배열을 다시 불러올 수 없다는 것이다... (아님 가능한데, 내 한계였던 것인가?)

package 백준5427;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class 불 {
	static char[][] map,mapCopy;
	static List<Space> exit;
	static int[][] me;
	static int w,h;
	
	static class Space{
		int r;
		int c;
		public Space(int r, int c) {
			super();
			this.r = r;
			this.c = c;
		}
		
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int t = sc.nextInt();// test case
		for (int T = 1; T < t + 1; T++) {
			w = sc.nextInt();
			h = sc.nextInt();
			
			//초기화
			map = new char[h][w];
			mapCopy = new char[h][w];
			exit = new ArrayList<>();
			me = new int[1][2];//내위치
			for(int i=0;i<h;i++) {
				String info = sc.next();
				for(int j=0;j<w;j++) {
					map[i][j]=info.charAt(j);
					mapCopy[i][j]=info.charAt(j);
					//내가 있는 곳 찾기
					if(map[i][j]=='@') {
						me[0][0]=i;
						me[0][1]=j;
					}
				}
			}
			
			//탈출구 찾기
			for(int i=0;i<h;i++) {
				for(int j=0;j<w;j++) {
					if(i==0 || i==h-1 || j==0 || j==w-1) {
						if(map[i][j]=='.') exit.add(new Space(i,j));
					}
				}
			}
			
			//탈출구가 없으면 게임 끝
			if(exit.size()==0) {
				System.out.println("IMPOSSIBLE");
				continue;//다음 테스트 케이스 이동
			}
			
			//시작
			Run(me[0][0],me[0][1]);
	
		} // test case end

	}
	
	public static boolean Run(int startR, int startC) {
		int[][] drc= {{-1,0},{1,0},{0,-1},{0,1}};//상 하 좌 우
		//불을 만나면 false
		if(mapCopy[startR][startC]=='*') return false;
		
		//탈출구를 만나면 true
		if(startR==0 || startR==h-1 || startC==0 || startC==w-1) {
			if(mapCopy[startR][startC]=='.') {
				//탈출구 만남
				return true;
			}
		}
		
		//달릴 위치 정하기 전에 불일어날 곳 예측 및 표시
		char[][] changeMap=fire(mapCopy);
		
		for(int d=0;d<4;d++) {
			int row = startR + drc[d][0];
			int col = startC + drc[d][1];
			if(row<0||row>=h||col<0||col>=w) continue;//경계체크
			if(changeMap[row][col]=='*' || changeMap[row][col]=='#') continue;//이미 불이 있거나 벽에는 사람이 못가므로 생략
			if(changeMap[row][col]=='.') Run(row,col);
		}
		return true;
	}

	public static char[][] fire(char[][] mapCopy) {
		int[][] drc= {{-1,0},{1,0},{0,-1},{0,1}};//상 하 좌 우
		//전체 탐색하고 불을 찾으면 4방으로 불을 붙인다.
		for(int i=0;i<h;i++) {
			for(int j=0;j<w;j++) {
				if(mapCopy[i][j]=='*') {
					for(int d=0;d<4;d++) {
						int row = i+drc[d][0];
						int col = j+drc[d][1];
						if(row<0||row>=h||col<0||col>=w) continue;//경계체크
						if(mapCopy[row][col]=='*' || mapCopy[row][col]=='#') continue;//이미 불이 있거나 벽에는 불을 못 붙이므로 생략
						mapCopy[row][col]='*';
					}
				}
			}
		}
		return mapCopy;
	}
}

 이런식으로 macCopy로 해결해보려 했으나 ... 있으나 없으나 원본훼손 상태에서 돌릴 수 없는 것은 마찬가지다 ^^

 

 

2) 성공한 설계

그리하여 나는 같은 시간대에서 갈 수 있는 지점을 전부 체크하고 다음 시간대로 갈 수있는 BFS로 풀어야 한다는 것을 깨달았다.

 

1) 현 상황을 입력받을 배열은 만들고자 하는 크기의 +2씩 더 더해준다. 탈출구가 배열 밖이기 때문이다.

- 나는 처음에 딱 맞는 크기로 배열을 만들고 경계에 '.' 갈 수 있는 공간이 있다면 탈출 성공이라고 했다. 하지만 다음과 같은 반례에서 +2씩 더해줘야겠다고 바로 생각했다.

반례
1
1 1
@

불이 없고, 오로지 나만있는 크기 1의 공간에서는 '.'이 존재하지 않기 때문에 배열의 크기를 더 크게 잡아야겠다고 생각했다.

 

 

2) 데이터를 입력받을 때 '내가 있는 위치'와 '불이 발생한 위치'를 기록한다.

- 처음엔 배열을 전부 돌면서 불이 있는 장소에 4방탐색까지 해주었는데 시간 초과가 나버렸다. 때문에 불이 있는 위치만 쏙쏙 골라서 4방탐색을 하고, 새로 생긴 불 데이터를 새롭게 저장하는 방향으로 시간을 줄였다. 여기서 이전에 있던 불 위치 정보는 버리고, 새로운 불 정보만 새롭게 가져가야 한다. 왜냐하면, 불이 나서 4방 탐색까지 완료한 곳에 또 불이 났다고 체크해 줄 필요가 없기 때문이다.

public static void fire() {
	int[][] drc = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };// 상 하 좌 우
		
	// 불이 난 곳 4방 처리 -> 새롭게 불이 추가된 곳 fire에 추가
	for (int i = fire.size() - 1; i >= 0; i--) {
		Space cur = fire.remove(i);// 불이 나서 4방 체크해준 곳에서 또 불이 날일은 없으니 제거
		for (int d = 0; d < 4; d++) {
			int row = cur.r + drc[d][0];
			int col = cur.c + drc[d][1];

			if (row < 1 || row > h || col < 1 || col > w)
				continue;// 경계체크
			if (map[row][col] == '*' || map[row][col] == '#')
				continue;// 이미 불이 있거나 벽에는 불을 못 붙이므로 생략 '*'불 자체가 이미 방문처리 되었다는 뜻
			map[row][col] = '*';
			fire.add(new Space(row, col, 0));
		}
	}
}

 

 

3) 내가 있는 위치부터 시작해 BFS함수(Run함수)를 돌린다.

 

 

4) 갈 수 있는 위치를 저장할 q를 만들고, 이미 갔던 부분을 체크하기 위해 visited배열을 만든다.

- 탈출할 곳으로 이미 갔던 곳을 다시 갈 필요는 없다.

- 이 때 내가 처음 있는 위치를 q에 넣고, visited 처리를 해준다.

 

 

5) 같은 시간대에 같은 지도 배열을 쓰기 위해 prevTime변수를 이용한다.

- 예를 들어 우리는 1초에 갈 수 있는 곳에서 2초에 갈 수 있는 곳을 선정해 큐에 넣어준다. 이때 2초에 갈 수 있는 곳은 여러 개 일 수 있다.

- 하나의 큐를 뽑기 위해 while을 찍고 돌아오는데, 그 때마다 불이 번지는 함수를 작동시키면 안되기 때문에 큐에 들어간 위치의 Space 클래스 안 time과 Run함수의 prevTime변수를 이용하여 이전 시간을 기록하고, 큐에서 새로운 시간이 등장하면 (2초 이후의 시간) 불을 그 때 번지게 했다.

 

 

6) 큐를 뽑았을 때 배열 밖의 범위이면 탈출 성공이다.

- 이 때 뽑힌 큐에서 여기 위치까지 오는 데 걸린 시간을 cur.time으로 꺼내줄 것이다. (cur은 현재 큐에서 뽑은 값)

- BFS이기 때문에 큐 앞에 있을수록 낮은 시간대이다. 때문에 탈출구를 찾았다면 바로 종료해줘도 된다.

- 해당 조건문에 걸리면 true를 반환하고, 해당 조건문을 한 번도 거치지 못한다면 false를 반환한다. 

 

 

7) 불은 현재 위치에서 사람이 탈출할 수 있는 곳을 찾기 위한 4방탐색을 하기 전에 퍼뜨린다.

- 불이 날 곳을 미리 예측해서 불이 날 것이라고 판단되면 사람이 못가기 떄문이다.

 

 

8) 4방 탐색을 시작한다.

- 내가 탈출할 수 있는 탈출로를 선정해서 큐에 넣는다. 또한 visited=true도 체크해준다.

- 그 전에 내가 가려고 하는 곳에 불과 벽이 있으면 가지 못한다. 또한 이미 방문한 위치도 가지 못한다.

 

 

---

3. 전체 코드

---

 

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	static char[][] map;
	static List<Space> exit, fire;
	static int[][] me;
	static int w, h;
	static int ResultTime;

	static class Space {
		int r;
		int c;
		int time;// 내가 이 위치를 몇 초만에 도착했는가

		public Space(int r, int c, int time) {
			super();
			this.r = r;
			this.c = c;
			this.time = time;
		}

	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int t = sc.nextInt();// test case
		for (int T = 1; T < t + 1; T++) {
			w = sc.nextInt();
			h = sc.nextInt();

			// 초기화
			map = new char[h + 2][w + 2];// 테두리는 탈출구임
			exit = new ArrayList<>();
			fire = new ArrayList<>();
			me = new int[1][2];// 내위치

			for (int i = 1; i <= h; i++) {
				String info = sc.next();
				for (int j = 1; j <= w; j++) {
					map[i][j] = info.charAt(j-1);

					// 내가 있는 곳 찾기
					if (map[i][j] == '@') {
						me[0][0] = i;
						me[0][1] = j;
					}
					// 불이 있는 곳 저장
					if (map[i][j] == '*') {
						fire.add(new Space(i, j, 0));
					}
				}
			}

			// 시작
			if (Run(me[0][0], me[0][1], 0)) {
				// 탈출성공
				System.out.println(ResultTime);
			} else {
				// 탈출실패
				System.out.println("IMPOSSIBLE");
			}
		} // test case end

	}

	// BFS
	public static boolean Run(int startR, int startC, int time) {
		int[][] drc = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };// 상 하 좌 우
		boolean[][] visited = new boolean[h+2][w+2];
		Queue<Space> q = new LinkedList<>();

		int prevTime = -1;
		q.add(new Space(startR, startC, time));
		visited[startR][startC] = true;

		while (!q.isEmpty()) {
			Space cur = q.poll();// 현재 위치
			if (cur.r == 0 || cur.r == h + 1 || cur.c == 0 || cur.c == w + 1) {
				// 탈출구
				ResultTime = cur.time;
				return true;
			}

			// 이전 시간초와 다른시간대면 fire 예측
			if (cur.time != prevTime) {
				fire();// 탈출로를 선정하기 위해 미리 불이 붙을 곳을 표시한다.
			}
			prevTime = cur.time;
			for (int d = 0; d < 4; d++) {
				int row = cur.r + drc[d][0];
				int col = cur.c + drc[d][1];
				if (map[row][col] == '*' || map[row][col] == '#' || visited[row][col])
					continue;// 불이나 벽이 있으면 못감, 이미 방문한 위치여도 못감
				q.add(new Space(row, col, cur.time + 1));
				visited[row][col] = true;
			}
		}

		return false;
	}

	public static void fire() {
		int[][] drc = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };// 상 하 좌 우
		
		// 불이 난 곳 4방 처리 -> 새롭게 불이 추가된 곳 fire에 추가
		for (int i = fire.size() - 1; i >= 0; i--) {
			Space cur = fire.remove(i);// 불이 나서 4방 체크해준 곳에서 또 불이 날일은 없으니 제거
			for (int d = 0; d < 4; d++) {
				int row = cur.r + drc[d][0];
				int col = cur.c + drc[d][1];

				if (row < 1 || row > h || col < 1 || col > w)
					continue;// 경계체크
				if (map[row][col] == '*' || map[row][col] == '#')
					continue;// 이미 불이 있거나 벽에는 불을 못 붙이므로 생략 '*'불 자체가 이미 방문처리 되었다는 뜻
				map[row][col] = '*';
				fire.add(new Space(row, col, 0));
			}
		}
	}
}

 

---

반례 찾기에 어려움을 겪는 나...

스스로 반례를 찾아보는연습을 더 하자

화이팅!