[BaekJoon] 5427번 - 불 [Java][C++]

문제 링크

---

1. 문제 풀이

최단 거리 BFS를 활용하면 해결할 수 있는 문제로 BFS로 상근이를 이동시키면서 동시에 불도 이동을 시켜주는 방식으로 해결했다. 불이 붙으려는 칸으로도 이동할 수 없으므로 불을 먼저 이동시키고 상근이를 이동시켜줬다.

---

2. 코드

1. 풀이 [Java]

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

public class Main {

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

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine());
        for (int tc = 1; tc <= T; tc++) {
            st = new StringTokenizer(br.readLine());
            int w = Integer.parseInt(st.nextToken());
            int h = Integer.parseInt(st.nextToken());

            char[][] map = new char[h][w];
            int sr = -1;
            int sc = -1;
            Queue<int[]> q = new ArrayDeque<>();

            for (int i = 0; i < h; i++) {
                map[i] = br.readLine().toCharArray();

                for (int j = 0; j < w; j++) {
                    if (map[i][j] == '@') {
                        sr = i;
                        sc = j;
                    } else if (map[i][j] == '*') {
                        q.offer(new int[]{i, j});
                    }
                }
            }

            int result = bfs(sr, sc, q, h, w, map);
            if (result == -1) {
                sb.append("IMPOSSIBLE\n");
            } else {
                sb.append(result).append("\n");
            }
        }

        System.out.println(sb);
    }

    static int bfs(int sr, int sc, Queue<int[]> fire, int h, int w, char[][] map) {
        Queue<int[]> q = new ArrayDeque<>();
        q.offer(new int[]{sr, sc});

        boolean[][] visited = new boolean[h][w];
        visited[sr][sc] = true;

        int dist = 0;

        while (!q.isEmpty()) {
            int size = fire.size();

            while (size-- > 0) {
                int[] node = fire.poll();

                for (int d = 0; d < 4; d++) {
                    int nr = node[0] + dr[d];
                    int nc = node[1] + dc[d];

                    if (nr < 0 || nr >= h || nc < 0 || nc >= w) continue;
                    if (map[nr][nc] == '#' || map[nr][nc] == '*') continue;

                    fire.offer(new int[]{nr, nc});
                    map[nr][nc] = '*';
                }
            }

            size = q.size();
            while (size-- > 0) {
                int[] node = q.poll();
                if (node[0] == 0 || node[0] == h - 1 || node[1] == 0 || node[1] == w - 1) return dist + 1;

                for (int d = 0; d < 4; d++) {
                    int nr = node[0] + dr[d];
                    int nc = node[1] + dc[d];

                    if (nr < 0 || nr >= h || nc < 0 || nc >= w) continue;
                    if (map[nr][nc] != '.' || visited[nr][nc]) continue;

                    q.offer(new int[]{nr, nc});
                    visited[nr][nc] = true;
                }
            }

            dist++;
        }

        return -1;
    }
}

2. 풀이 [C++]

#include <bits/stdc++.h>
using namespace std;

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

int h, w;
char grid[1000][1000];
bool visited[1000][1000];

int bfs(int sr, int sc, queue<pair<int, int>>& fire) {
    queue<pair<int, int>> q;
    q.push({sr, sc});

    visited[sr][sc] = true;

    int dist = 0;

    while (!q.empty()) {
        int sz = fire.size();

        while (sz--) {
            auto [r, c] = fire.front();
            fire.pop();

            for (int d = 0; d < 4; d++) {
                int nr = r + dr[d];
                int nc = c + dc[d];

                if (nr < 0 || nr >= h || nc < 0 || nc >= w) continue;
                if (grid[nr][nc] == '#' || grid[nr][nc] == '*') continue;

                fire.push({nr, nc});
                grid[nr][nc] = '*';
            }
        }

        sz = q.size();
        while (sz--) {
            auto [r, c] = q.front();
            q.pop();

            if (r == 0 || r == h - 1 || c == 0 || c == w - 1) return dist + 1;

            for (int d = 0; d < 4; d++) {
                int nr = r + dr[d];
                int nc = c + dc[d];

                if (nr < 0 || nr >= h || nc < 0 || nc >= w) continue;
                if (grid[nr][nc] != '.' || visited[nr][nc]) continue;

                q.push({nr, nc});
                visited[nr][nc] = true;
            }
        }

        dist++;
    }

    return -1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    for (int tc = 1; tc <= t; tc++) {
        cin >> w >> h;

        memset(grid, 0, sizeof(grid));
        memset(visited, 0, sizeof(visited));

        int sr, sc;
        queue<pair<int, int>> q;

        for (int i = 0; i < h; i++) {
            string s;
            cin >> s;

            for (int j = 0; j < w; j++) {
                grid[i][j] = s[j];

                if (grid[i][j] == '@') {
                    sr = i;
                    sc = j;
                } else if (grid[i][j] == '*') {
                    q.push({i, j});
                }
            }
        }

        int res = bfs(sr, sc, q);
        if (res == -1) {
            cout << "IMPOSSIBLE\n";
        } else {
            cout << res << '\n';
        }
    }
}

---