문제

BOJ 4179: 불! https://www.acmicpc.net/problem/4179

풀이

• 입력을 받으며 지훈의 위치와 불의 위치를 Queue에 넣는다.
  • 지훈의 위치가 이미 map의 가장자리에 있으면 탈출할 수 있기 때문에 바로 처리해준다.
  • 여기서 불의 위치는 바로 Queue에 넣고 지훈의 위치는 bfs() 함수에 들어가서 넣는다.
  • 이유는 불에 탈 수 있는 위치에 지훈이 있으면 안되기 때문에 불 먼저 번지게 하고 지훈을 이동시킨다.
• bfs()를 수행한다.
  • 네 방향을 탐색하며 범위를 벗어나거나, 벽이거나, 불인 경우에는 continue;
  • !isVisited[nx][ny](아직 방문 안 함) 이고 지훈(type == 0) 이면 Queue에 넣어준다.
  • 불(type == 1)인 경우에는 Queue 에 넣어주고 그 위치를 F로 바꿔줘서 방문 체크를 해준다.

코드

import java.util.*;
import java.io.*;

public class Main {
	
	static int R, C;
	static char[][] map;
	static boolean[][] isVisited;
	static int[] dx = {0, 0, -1, 1};
	static int[] dy = {1, -1, 0, 0};
	static Queue<Pos> que = new LinkedList<>();
	static Pos jihoon; // 지훈이 위치, 타입, 횟수
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		
		map = new char[R][C];
		isVisited = new boolean[R][C];
	
		for(int i=0; i<R; i++) {
			String str = br.readLine();
			for(int j=0; j<C; j++) {
				map[i][j] = str.charAt(j);
				
				if(map[i][j] == 'J') {
					// 첫 위치부터 탈출이 가능하면
					if(i == 0 || j == 0 || i == R-1 || j == C-1) {
						System.out.println(1);
						return;
					}
					
					map[i][j] = '.'; // 지훈이의 첫 위치를 '.'으로 바꿈
					jihoon = new Pos(i, j, 0, 0);
				} else if(map[i][j] == 'F') {
					que.add(new Pos(i, j, 1, 0));
				}
			}
		}
		
		bfs();
		
	}
	
	static void bfs() {
		
		que.add(jihoon);
		isVisited[jihoon.x][jihoon.y] = true;
		
		while(!que.isEmpty()) {
			Pos p = que.poll();
			
			int curX = p.x;
			int curY = p.y;
			int cnt = p.cnt;
			
			// 가장자리 && 지훈(type == 0)
			if((curX == 0 || curY == 0 || curX == R-1 || curY == C-1) && p.type == 0) {
				System.out.println(cnt + 1);
				return;
			}
			
			for(int t=0; t<4; t++) {
				int nx = curX + dx[t];
				int ny = curY + dy[t];
				
				// 큐에 안 넣어도 되는 조건
				if(nx < 0 || ny < 0 || nx >= R || ny >= C || map[nx][ny] == '#' || map[nx][ny] == 'F') continue;
				
				if(p.type == 0 && !isVisited[nx][ny]) { // 지훈이
					que.add(new Pos(nx, ny, 0, cnt + 1));
					isVisited[nx][ny] = true;
				} else { // 불
					que.add(new Pos(nx, ny, 1, cnt + 1));
					map[nx][ny] = 'F';
				}
			}

		}	
		
		System.out.println("IMPOSSIBLE");
	}

	static class Pos{
		int x, y;
		int type; //0: 지훈, 1: 불
		int cnt;
		
		Pos(int x, int y, int type, int cnt){
			this.x = x;
			this.y = y;
			this.type = type;
			this.cnt = cnt;
		}
	}	
}

정리

• 이전에 지훈과 불을 다른 Queue에 넣어서 해결해보려고 했는데 틀렸다.
• 서로 다른 조건으로 BFS를 하는 방법을 배웠다.