[BOJ] 5427. 불 - BFS

제출일 : 2019-09-04

문제 풀이 시간 : 1H 15M

난이도 : ★★★

Problem

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

Input

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 최대 100개이다.

각 테스트 케이스의 첫째 줄에는 빌딩 지도의 너비와 높이 w와 h가 주어진다. (1 ≤ w,h ≤ 1000)

다음 h개 줄에는 w개의 문자, 빌딩의 지도가 주어진다.

• '.': 빈 공간
• '#': 벽
• '@': 상근이의 시작 위치
• '*': 불

각 지도에 @의 개수는 하나이다.

Output

각 테스트 케이스마다 빌딩을 탈출하는데 가장 빠른 시간을 출력한다. 빌딩을 탈출할 수 없는 경우에는 IMPOSSIBLE을 출력한다.

Example

input

5
4 3
####
#*@.
####
7 6
###.###
#*#.#*#
#.....#
#.....#
#..@..#
#######
7 4
###.###
#....*#
#@....#
.######
5 5
.....
.***.
.*@*.
.***.
.....
3 3
###
#@#
###

output

2
5
IMPOSSIBLE
IMPOSSIBLE
IMPOSSIBLE

Solution & Inpression

BFS 응용 문제.불이 먼저 퍼지고 사람이 이동. 한턴 한턴 수행하면 쉽게 풀리는 문제였지만 처음부터 생각하기 힘들었던 문제.

Code

언어 : JAVA

메모리 : 119,172 kb

실행시간 : 720 ms

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

public class Main {
    static class pos {
        int y;
        int x;

        pos(int y, int x) {
            this.y = y;
            this.x = x;
        }
    }

    public static void main(String[] args) throws IOException {
        //System.setIn(new FileInputStream("res/백준_5427_불.txt"));
        int dy[] = { -1, 1, 0, 0 };
        int dx[] = { 0, 0, 1, -1 };
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int T = Integer.parseInt(br.readLine());
        Queue<pos> fire = new LinkedList<>();
        Queue<pos> me = new LinkedList<>();
        for (int tc = 1; tc <= T; tc++) {
            me.clear();
            fire.clear();
            boolean flag = false;
            st = new StringTokenizer(br.readLine());
            int w = Integer.parseInt(st.nextToken());
            int h = Integer.parseInt(st.nextToken());
            char[][] map = new char[h][w];
            boolean[][] visit = new boolean[h][w];
            int py = 0, px = 0, flame = 0, per = 0;
            for (int y = 0; y < h; y++) {
                map[y] = br.readLine().toCharArray();
                for (int x = 0; x < w; x++) {
                    if (map[y][x] == '*') {
                        fire.offer(new pos(y, x));
                    } else if (map[y][x] == '@') {
                        visit[y][x] = true;
                        me.offer(new pos(y, x));
                        map[y][x] = '.';
                    }
                }
            }
            int result = 0;
            while (!me.isEmpty()) {
                result++;
                flame = fire.size();
                for (int f = 0; f < flame; f++) {// 불을 먼저 붙여버리겠음
                    int y = fire.peek().y;
                    int x = fire.peek().x;
                    fire.poll();
                    for (int i = 0; i < 4; i++) {
                        int ny = y + dy[i];
                        int nx = x + dx[i];
                        if (ny >= 0 && nx >= 0 && ny < h && nx < w && map[ny][nx] == '.') {
                            map[ny][nx] = '*';
                            fire.offer(new pos(ny, nx));
                        }
                    }
                }

                per = me.size();
                for (int pidx = 0; pidx < per; pidx++) {
                    py = me.peek().y;
                    px = me.peek().x;
                    me.poll();
                    if ((py == 0 || px == 0 || py == h - 1 || px == w - 1)) { // 다음번에 바로간다
                        flag = true;
                        me.clear();
                        break;
                    }
                    for (int i = 0; i < 4; i++) {
                        int npy = py + dy[i];
                        int npx = px + dx[i];
                        if (npy >= 0 && npx >= 0 && npy < h && npx < w && map[npy][npx] == '.' && !visit[npy][npx]) {
                            me.offer(new pos(npy, npx));
                            visit[npy][npx] = true;
                        }
                    }
                }
            }
            if (flag)
                System.out.println(result);
            else
                System.out.println("IMPOSSIBLE");
        }
    }
}

[BOJ] 6593. 상범빌딩 - BFS

제출일 : 2019-09-23

문제 풀이 시간 : 1H

난이도 : ★★★

Problem

link : https://www.acmicpc.net/problem/6593

Input

입력은 여러 개의 테스트 케이스로 이루어지며, 각 테스트 케이스는 세 개의 정수 L, R, C로 시작한다. L(1 ≤ L ≤ 30)은 상범 빌딩의 층 수이다. R(1 ≤ R ≤ 30)과 C(1 ≤ C ≤ 30)는 상범 빌딩의 한 층의 행과 열의 개수를 나타낸다.

그 다음 각 줄이 C개의 문자로 이루어진 R개의 행이 L번 주어진다. 각 문자는 상범 빌딩의 한 칸을 나타낸다. 금으로 막혀있어 지나갈 수 없는 칸은 '#'으로 표현되고, 비어있는 칸은 '.'으로 표현된다. 당신의 시작 지점은 'S'로 표현되고, 탈출할 수 있는 출구는 'E'로 표현된다. 각 층 사이에는 빈 줄이 있으며, 입력의 끝은 L, R, C가 모두 0으로 표현된다.

Output

각 빌딩에 대해 한 줄씩 답을 출력한다. 만약 당신이 탈출할 수 있다면 다음과 같이 출력한다.

Escaped in x minute(s).

여기서 x는 상범 빌딩을 탈출하는 데에 필요한 최단 시간이다.

만일 탈출이 불가능하다면, 다음과 같이 출력한다.

Trapped!

Example

input

3 4 5
S....
.###.
.##..
###.#

#####
#####
##.##
##...

#####
#####
#.###
####E

1 3 3
S##
#E#
###

0 0 0

output

Escaped in 11 minute(s).
Trapped!

Solution & Inpression

2차원 배열의 BFS문제들과 비슷하게 풀어나갔다. 다만 탐색을 6방향으로 해야 문제를 해결할 수 있다.

Code

언어 : JAVA

메모리 : 18,104kb

실행시간 : 148ms

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

public class Main {
    static int L, R, C;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        while (true) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            L = Integer.parseInt(st.nextToken());
            R = Integer.parseInt(st.nextToken());
            C = Integer.parseInt(st.nextToken());

            if (L == 0)
                break;

            char[][][] building = new char[L][R][C];
            boolean visit[][][] = new boolean[L][R][C];
            Queue<int[]> q = new LinkedList<int[]>();
            for (int k = 0; k < L; k++) {
                for (int i = 0; i < R; i++) {
                    String str = br.readLine();
                    for (int j = 0; j < C; j++) {
                        char cur = str.charAt(j);
                        building[k][i][j] = cur;
                        if (cur == 'S') {
                            q.offer(new int[] { k, i, j, 0 });
                            visit[k][i][j] = true;
                        }
                    }
                }
                br.readLine();
            } // 입력 끝

            int[] dk = { -1, 1, 0, 0, 0, 0 };
            int[] dx = { 0, 0, -1, 1, 0, 0 };
            int[] dy = { 0, 0, 0, 0, -1, 1 };
            int res = Integer.MAX_VALUE;

            while (!q.isEmpty()) {
                int[] cur = q.poll();
                 //System.out.println(Arrays.toString(cur));
                if (building[cur[0]][cur[1]][cur[2]] == 'E') {
                    res = (cur[3] > res) ? res : cur[3];
                    continue;
                }
                for (int k = 0; k < 6; k++) {
                    int l = cur[0] + dk[k];
                    int x = cur[1] + dx[k];
                    int y = cur[2] + dy[k];
                    if (range(l, x, y) && !visit[l][x][y] && building[l][x][y] != '#') {
                        visit[l][x][y] = true;
                        q.offer(new int[] { l, x, y, (cur[3] + 1) });
                    }
                }
            }
            System.out.println((res == Integer.MAX_VALUE) ? "Trapped!" : "Escaped in " + res + " minute(s).");

        }
    }

    private static boolean range(int l, int x, int y) {
        if (0 <= l && l < L && 0 <= x && x < R && 0 <= y && y < C)
            return true;
        return false;
    }
}