BOJ5427 불

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

5427번: 불

bfs 두번 쓰는 문제, 몇초(step)을 저장하는 방식은 두가지이다. 이 경우에는 visited에 시간을 기록하는 방법을 쓰면 쉽다.

import java.io.*;
import java.util.*;
public class Main
{
    static int r;
    static int c;
    static String[][] map;
    static int[][] fire_visited ;
    
    
    public static void fire_bfs(Queue<Node> q){
        int[] move_c = {0, 0, 1, -1};
        int[] move_r = {1, -1, 0, 0};
        
        while(q.size()>0){
            Node node = q.poll();
            for(int i=0;i<4;i++){
                Node next = new Node(node.r+move_r[i],node.c+ move_c[i],node.step+1);
                if(next.r>=0 && next.c>=0 && next.r< r && next.c < c){
                    if(fire_visited[next.r][next.c]==0 && (map[next.r][next.c].equals(".") || map[next.r][next.c].equals("@"))){
                        fire_visited[next.r][next.c] = next.step;
                        q.offer(next);
                    }
                }
            }
        }

    }
    public static int person_bfs(Queue<Node> q){
        boolean[][] visited = new boolean[r][c];
        int[] move_c = {0, 0, 1, -1};
        int[] move_r = {1, -1, 0, 0};
        
        while(q.size()>0){
            Node node = q.poll();
            if(node.r==r-1 || node.r==0 || node.c==c-1 ||node.c==0){
                return node.step;
            }
            visited[node.r][node.c] = true;
            for(int i=0;i<4;i++){
                Node next = new Node(node.r+move_r[i],node.c+move_c[i],node.step+1);
                if(next.r>=0 && next.c>=0 && next.r< r && next.c < c){
                    if((next.step<fire_visited[next.r][next.c] || fire_visited[next.r][next.c]==0) && map[next.r][next.c].equals(".") && !visited[next.r][next.c]){
                        visited[next.r][next.c] = true;
                        q.offer(next);
                    }
                }
            }
        }
        return 0;

    }
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int t= Integer.parseInt(br.readLine());
		
		while(t-->0){
		    String[] input1 = br.readLine().split(" ");
		    c = Integer.parseInt(input1[0]);
		    r = Integer.parseInt(input1[1]);
		    map = new String[r][c];
		    fire_visited = new int[r][c];
		    Queue<Node> person_q = new LinkedList();
		    Queue<Node> fire_q = new LinkedList();
		    
		    for(int i=0; i<r;i++){
		        String[] input2 =br.readLine().split("");
		        for (int j=0; j<c;j++){
		            map[i][j] = input2[j];
		            if(input2[j].equals("*")){
		                fire_q.offer(new Node(i,j,1));
		                fire_visited[i][j] = 1;
		            }
		            if(input2[j].equals("@")){
		                person_q.offer(new Node(i,j,1));
		            }
		            
		        }
		    }
		    
		    fire_bfs(fire_q);
		    int ans = person_bfs(person_q);
		    if(ans>0){
		        System.out.println(ans);
		    }else{
		        System.out.println("IMPOSSIBLE"); 
		    }
		}
		
        
        
        
	}
	
	public static class Node{
	    int r;
	    int c;
	    int step;
	    public Node(int r ,int c ,int step){
	        this.r = r;
	        this.c = c;
	        this.step=step;
	    }
	    public String toString(){
	        return "["+ r+", "+c+", "+step+" ]";
	    }
	}
}

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

class Main {
    static int[][] visited;
    static int[][] fire;
    static int n, m;

    static int[] dr = {-1, 1, 0, 0};
    static int[] dc = {0, 0, -1, 1};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int tc = sc.nextInt();
        for (int t = 0; t < tc; t++) {
            n = sc.nextInt();
            m = sc.nextInt();
            visited = new int[m][n];
            fire = new int[m][n];
            Queue<Point> q = new LinkedList<>();
            Queue<Point> fireQ = new LinkedList<>();
            for (int i = 0; i < m; i++) {
                String line = sc.next();
                for (int j = 0; j < n; j++) {
                    char c = line.charAt(j);
                    if (c == '#') {
                        fire[i][j] = visited[i][j] = -1;
                    } else if (c == '@') {
                        q.add(new Point(i, j));
                        visited[i][j] = 1;
                    } else if (c == '*') {
                        fireQ.add(new Point(i, j));
                        fire[i][j] = 1;
                    }
                }
            }
            // 불을 먼저 질러서 언제 불이 전파되는지 기록한다
            while (!fireQ.isEmpty()) {
                Point now = fireQ.poll();
                for (int i = 0; i < 4; i++) {
                    int nr = now.r + dr[i];
                    int nc = now.c + dc[i];
                    if (isOutOfRange(nr, nc)) continue;
                    if (fire[nr][nc] == 0) {
                        fire[nr][nc] = fire[now.r][now.c] + 1;
                        fireQ.add(new Point(nr, nc));
                    }
                }
            }


            boolean isEscaped = false;
            while (!q.isEmpty()) {
                Point now = q.poll();
                if (isExit(now.r, now.c)) {
                    System.out.println(visited[now.r][now.c]);
                    isEscaped = true;
                    break;
                }
                for (int i = 0; i < 4; i++) {
                    int nr = now.r + dr[i];
                    int nc = now.c + dc[i];
                    if (isOutOfRange(nr, nc)) continue;
                    if (visited[nr][nc] != 0) continue;
                    if (fire[nr][nc] == 0 || fire[nr][nc] > visited[now.r][now.c] + 1) {
                        visited[nr][nc] = visited[now.r][now.c] + 1;
                        q.add(new Point(nr, nc));
                    }
                }
            }
            if (!isEscaped) {
                System.out.println("IMPOSSIBLE");
            }
        }

    }

    static boolean isOutOfRange(int r, int c) {
        return r < 0 || r >= m || c < 0 || c >= n;
    }

    static boolean isExit(int r, int c) {
        return r == 0 || r == m - 1 || c == 0 || c == n - 1;
    }
}

class Point {
    int r, c;

    public Point(int r, int c) {
        this.r = r;
        this.c = c;
    }
}