[백준] 5247. 불 (자바 JAVA)

[ 문제 ]  [백준] 5247. 불 (자바 JAVA)

 

문제 링크 : https://www.acmicpc.net/problem/5427

5427번: 불

---

# 접근 방법 및 풀이 

 

• 구현 시뮬 문제다. 근데 정답률이 22퍼길래 잔뜩 쫄아서 풀었는데 다행히 한번만에 맞췄다.
• bfs로 풀었고, 정답률 낮은 이유가 visit배열 때문일 것 같다. visit배열을 3차원 배열로 해서 불일 경우와 상근이일 경우로 나누어서 방문체크를 해주어야한다. -> visit[n][m][2]
• 벽 뚫고 이동하기 시리즈를 풀어봤다면 그래도 쉬웠을 문제다!
• 큐에 불과 상근이의 위치를 둘다 넣지만 불 먼저 넣어주어야한다. 그래야 같은 depth일 때 불이 먼저 퍼지기 때문에 불이 다음으로 이동할 곳에 상근이가 가지 못한다. 반대로 상근이가 이미 간 곳이더라도 불은 갈 수 있다.
• 여기서 중요한건 불의 위치가 여러개 있기 때문에 불의 위치를 list에 담고 큐에 list에 담긴 불의 위치 먼저 담아주고 그다음 상근이의 위치를 넣었다.
• bfs를 돌면서 큐에 담긴게 불일 경우와 상근이일 경우로 나누어 분기를 해주었다.
• 상근이일 경우에 다음에 가려는 위치에 불이 이미 있는지 visit체크를 해주어야하고, 상근이가 map범위 밖으로 나갔을 경우 탈출에 성공한 것이기 때문에 cnt+1을 해주면 된다.
• 불일 경우엔 map범위 밖으로 나간 것은 갈 수 없기 때문에 처리를 해준다.
• 자세한건 코드참조

# 주의할 점 

 

• 불이 더 먼저 퍼져야함
• visit 방문체크 상근이일때와 불일때 나누어서 방문체크 해주기

 

JAVA 코드

package Gold;

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

public class bj5247_불 {
	static class Node{
		int r, c, cnt;
		boolean fire;
		public Node(int r, int c, int cnt, boolean fire) {
			this.r = r;
			this.c = c;
			this.cnt = cnt;
			this.fire = fire;
		}
	}
	static int dr[] = {-1, 1, 0, 0};
	static int dc[] = {0, 0, -1, 1};
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(in.readLine());
		out: for (int tc = 1; tc <= T; tc++) {
			StringTokenizer st = new StringTokenizer(in.readLine());
			int m = Integer.parseInt(st.nextToken());
			int n = Integer.parseInt(st.nextToken());
			char map[][] = new char[n][m];
			Queue<Node> queue = new LinkedList<Node>();
			List<Node> fire = new ArrayList<Node>();
			boolean visit[][][] = new boolean[n][m][2];
			int r = 0, c = 0;
			for (int i = 0; i < n ; i++) {
				String s = in.readLine();
				for (int j = 0; j < m; j++) {
					map[i][j] = s.charAt(j);
					if(map[i][j] == '*')
						fire.add(new Node(i, j, 0, true));
					if(map[i][j] == '@') {
						r = i;
						c = j;
					}		
				}
			}//end for
			for (int i = 0; i < fire.size(); i++) {
				Node node = fire.get(i);
				queue.add(node);
				visit[node.r][node.c][1] = true;
			}
			queue.add(new Node(r, c, 0, false));
			visit[r][c][0] = true;
			String answer = "IMPOSSIBLE";
			while(!queue.isEmpty()) {
				Node node = queue.poll();
				for (int d = 0; d < 4; d++) {
					int nr = node.r + dr[d];
					int nc = node.c + dc[d];
					if(node.fire) {
						if(nr < 0 || nc < 0 || nr >= n || nc >= m || visit[nr][nc][1] || map[nr][nc] == '#')
							continue;
						visit[nr][nc][1] = true;
						queue.add(new Node(nr, nc, node.cnt+1, true));
					}else {
						if(nr < 0 || nc < 0 || nr >= n || nc >= m) {
							System.out.println(node.cnt+1);
							continue out;
						}
						if(visit[nr][nc][0] || visit[nr][nc][1] || map[nr][nc] == '#')
							continue;
						visit[nr][nc][0] = true;
						queue.add(new Node(nr, nc, node.cnt+1, false));
					}
				}
			}
			System.out.println(answer);
		}
	}
}

 

 

 

REVIEW