[Java Algorithm] 불 BOJ #5427

문제

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

5427번: 불

 

내 문제 풀이

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

public class Main {
	
	static Deque<int[]> que; // {상근 or 불 여부, sec, x좌표, y좌표} (상근: 0, 불: 1)
	static int[] dx = {0, 0, -1, 1};
	static int[] dy = {-1, 1, 0, 0};
	static int h, w;
	static char[][] map;
	
	public static int bfs() {
		while(!que.isEmpty()) {
			int[] now = que.removeFirst();
			int type = now[0];
			int sec = now[1];
			int x = now[2];
			int y = now[3];
			
			findLoop:
			for(int i = 0; i < 4; i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];
				
				if(type == 0) { // 상근이
					if(nx < 0 || ny < 0 || nx >= h || ny >= w) return sec+1; // 탈출 성공
					if(map[nx][ny] != '.') continue findLoop; // 빈 곳 아닐 때
					que.add(new int[]{type, sec+1, nx, ny});
					map[nx][ny] = '@';
				}
				else { // 불
					if(nx < 0 || ny < 0 || nx >= h || ny >= w || map[nx][ny] != '.') continue findLoop;
					que.add(new int[]{type, sec+1, nx, ny});
					map[nx][ny] = '*';
				}
			}
		}
		return -1;
	}

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuffer out = new StringBuffer();
		
		int tc = Integer.parseInt(in.readLine());
		
		for(int t = 0; t < tc; t++) {
			st = new StringTokenizer(in.readLine());
			w = Integer.parseInt(st.nextToken());
			h = Integer.parseInt(st.nextToken());
			
			int[] startPoint = new int[3]; // 상근이 정보 잠시 저장할 용도
			map = new char[h][w];
			que = new ArrayDeque<>();
			
			for(int i = 0; i < h; i++) {
				String tmp = in.readLine();
				for(int j = 0; j < w; j++) {
					map[i][j] = tmp.charAt(j);
					if(tmp.charAt(j) == '*') que.add(new int[]{1, 0, i, j});
					else if(tmp.charAt(j) == '@') startPoint = new int[]{0, 0, i, j};
				}
			}
			que.add(startPoint); // 상근이를 맨 뒤에 추가하기 위함
			
			int result = bfs();
			if(result == -1) System.out.println("IMPOSSIBLE");
			else System.out.println(result);
		}
	}

}

👉 BFS 문제

 

[ 문제 풀기 전 체크 ! ]

✔️ 상근이는 단 한 명이고, 불처럼 퍼지는 존재가 아니지만, 불처럼 퍼뜨려주는 방법을 택했다.

그 이유는! 상근이가 지나갔던 자리는 추후에 추후에 오더라도 아무런 의미가 없으며,

상근이가 가는 자리마다 @를 표시해주어 자취를 남기면 이는 방문 체크처럼 사용할 수 있기 때문에,

불의 의미없는 퍼짐을 방지하여 효율을 높일 수 있기 때문이다.

=> visited 배열 필요 x

 

✔️ 불이 앞으로 퍼져 나갈 예정인 자리에도 상근이는 갈 수 없으므로,

불을 먼저 퍼뜨린 후 상근이를 움직이는 방법을 사용했다.

 

[ 문제 풀이 ]

• bfs 탐색을 위하여 que라는 덱을 만들어주었고, int형 배열을 요소로 가지도록 했다.
  저장되는 int형 배열은 {type, sec, x, y} 형태로 만들어주었는데, 아래와같이 정리할 수 있다.
  - type : 상근이는 0, 불은 1
  - sec : 해당 자리까지 퍼지는데 걸린 시간
  - x, y : 좌표
• 처음 지도에 대한 정보를 받을 때, 바로 불과 상근이의 위치를 파악하고 que에 넣어주었는데,
  상근이의 경우 불보다 나중에 움직이도록 하기 위해
  우선 startPoint 배열에 임시 저장, 모든 입력이 종료되었을 때 마지막으로  que에 add했다.
• bfs 탐색 시 현재 탐색하는 que 요소가 상근이일 경우와 불일 경우로 나누어주었다.
• 상근이의 경우 map 배열의 범위를 벗어나면 탈출에 성공한 것으로 간주, sec+1을 return했다.
  빈 곳을 만나지 못했을 때는 예외로 처리해주었고,
  빈 곳을 만났을 때는 새로운 탐색 위치를 que에 추가하고, 상근이의 움직임을 map에 표시했다.
• 불의 경우 map 배열의 범위를 벗어나거나 빈 곳을 만나지 못하였을 때 예외로 처리했고,
  빈 곳을 만났을 때는 que에 새로운 탐색 위치를 추가하고, 불의 움직임을 map에 표시했다.
• while문이 종료될 때까지 return하지 않았다면 상근이는 탈출에 실패했다는 뜻이므로
  -1을 리턴하도록 했고, 이 때는 IMPOSSIBLE을 출력했다.

 

💡 피드백

• BFS의 동작을 잘 이해하고 있다면 금방 풀 수 있는 문제같다.