<BOJ> 5427 자바 (불)

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

---

접근법

문제를 보면

불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동 할 수 없다.

상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동 할 수 있다.

라고 쓰여있는 걸 보면, 우선순위가 불의이동이 높다는 것을 알 수 있다.

 

따라서,

1. 불의 이동을 BFS로 구현하며 fireMap에 시간 찍어주기

2. 상근이 이동

  - 조건: 벽, 불의 이동시간보다 낮아야 통과, 맵을 벗어나면 return 

---

전체코드

package algorithms.src.searching;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class b5427_불 {
    private static int W;
    private static int H;
    private static int[] dy = {-1, 1, 0, 0};
    private static int[] dx = {0, 0, -1, 1};

    private static Queue<Node> fireQ = new LinkedList<>();
    private static PriorityQueue<Node> runnerQ = new PriorityQueue<>();
    private static char[][] map;
    private static int[][] fireMap;
    private static boolean[][] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        for (int t = 1; t <= T; t++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            W = Integer.parseInt(st.nextToken());
            H = Integer.parseInt(st.nextToken());

            fireQ = new LinkedList<>();
            runnerQ = new PriorityQueue<>();

            map = new char[H][W];
            fireMap = new int[H][W];
            for (int i = 0; i < H; i++) {
                Arrays.fill(fireMap[i], -1);
            }



            for (int i = 0; i < H; i++) {
                String str = br.readLine();
                for (int j = 0; j < W; j++) {
                    map[i][j] = str.charAt(j);
                    if(map[i][j] == '@') runnerQ.add(new Node(i, j, 0));
                    else if (map[i][j] == '*') {
                        fireQ.add(new Node(i, j, 0));
                        fireMap[i][j] = 0;
                    }
                }
            }
            visited = new boolean[H][W];

            fire();

            int ans = run();
            if (ans == -1) {
                System.out.println("IMPOSSIBLE");
            } else System.out.println(ans);
        }
    }

    private static int run() {
        while (!runnerQ.isEmpty()) {
            Node node = runnerQ.poll();
            for (int i = 0; i < 4; i++) {
                int ny = node.y + dy[i];
                int nx = node.x + dx[i];
                if(ny < 0 || ny >= H || nx < 0 || nx >= W) return node.time+1;
                if(map[ny][nx] == '#' || visited[ny][nx]) continue;
                if (fireMap[ny][nx] != -1 && fireMap[ny][nx] <= node.time + 1) continue;
                visited[ny][nx] = true;
                runnerQ.add(new Node(ny, nx, node.time + 1));
            }
        }
        return -1;
    }

    private static void fire() {
        while (!fireQ.isEmpty()) {
            Node fire = fireQ.poll();

            for (int i = 0; i < 4; i++) {
                int ny = fire.y + dy[i];
                int nx = fire.x + dx[i];
                if (ny < 0 || ny >= H || nx < 0 || nx >= W || fireMap[ny][nx] != -1 || map[ny][nx] == '#') {
                    continue;
                }
                fireMap[ny][nx] = fire.time + 1;
                fireQ.add(new Node(ny, nx, fire.time + 1));
            }
        }

    }

    private static class Node implements Comparable<Node>{
        int y;
        int x;
        int time;

        public Node(int y, int x, int time) {
            this.y = y;
            this.x = x;
            this.time = time;
        }

        @Override
        public int compareTo(Node o) {
            return this.time - o.time ;
        }
    }

}

 

---

12% 불기둥

 

상근이가 돌아다닐 때 조건을 잘못줘서 12%에서 계속 틀렸다...

                if (fireMap[ny][nx] != -1 && fireMap[ny][nx] <= node.time + 1) continue;
                visited[ny][nx] = true;
                if(fireMap[ny][nx] > node.time+1){
                    runnerQ.add(new Node(ny, nx, node.time + 1));
                }
            }

 

 

다음 좌표 fireMap의 값이 -1이 아닌 상황인데 firmMap의 값이 더 큰 경우에만 큐에 넣어주는 바보같은 코딩을 함