Easy is Perfect

[백준] 5427번 C/C++ 풀이 _ 불

  • melonicedlatte
  • Sep 17, 2018


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

불 성공

시간 제한메모리 제한제출정답맞은 사람정답 비율
1 초128 MB7260166598221.064%

문제

상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다.

매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에는 불이 붙지 않는다. 상근이는 동서남북 인접한 칸으로 이동할 수 있으며, 1초가 걸린다. 상근이는 벽을 통과할 수 없고, 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. 상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다.

빌딩의 지도가 주어졌을 때, 얼마나 빨리 빌딩을 탈출할 수 있는지 구하는 프로그램을 작성하시오.

입력

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

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

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

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

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

출력

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

예제 입력 1 

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

예제 출력 1 

2
5
IMPOSSIBLE
IMPOSSIBLE
IMPOSSIBLE

출처

ACM-ICPC > Regionals > Europe > Northwestern European Regional Contest > Benelux Algorithm Programming Contest > BAPC 2012 F번

  • 문제의 오타를 찾은 사람: adh0463
  • 데이터를 추가한 사람: b8goal
  • 문제를 번역한 사람: baekjoon

알고리즘 분류






































풀이

http://melonicedlatte.com/2018/09/17/023544.html 풀이와 굉장히 유사합니다. 
문제는 거의 동일하고, 테스트 케이스만 조금 늘어난 문제 형태입니다. 

알고리즘은 bfs를 이용하면 풀 수 있는 문제입니다. 
알고리즘을 모른다기보다는 시뮬레이션이라 구현이 다소 복잡한 문제였습니다. 

저 같은 경우에는 map에는 초기 배치를 저장했습니다. 
상근이가 방문한 곳을 저장하는 sanggeun_depth, 불이 방문한 곳을 저장하는 fire_depth 배열을 생성했습니다.
큐는 두 개를 사용하여 '불'과 '상근' 에 대한 각 단계의 bfs 를 진행했습니다. 

fire 큐에서 new_row와 new_col을 받은 다음에 인덱스 체크, 기존에 물이 차있었는지 여부, 비버 집인지, 돌인지를 체크합니다. 
상근 큐에서는 new_row와 new_col 을 받은 다음에 직전 단계에서 물이 차있었으면 상근이가 갈 수 없다고 판단하고 넘깁니다.
해당 구문을 통과하면 water 과 같이 조건 체크를 하고, new_row와 new_col 이 out of index 라면 정답이 됩니다. 

자세한 풀이는 소스코드를 참조해주세요~


소스코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
#define RC_MX 1000 + 1
#define SIDE 4
#pragma warning(disable:4996)

int is_can_escape() {
    char map[RC_MX][RC_MX] = { 0 };
    int sanggeun_depth[RC_MX][RC_MX];
    int fire_depth[RC_MX][RC_MX];
    int side_arr[SIDE][2] = { { -1,0 },{ 1,0 },{ 0,-1 },{ 0,1 } };
    queue<pair<int, int>> sanggeun_queue, fire_queue;
    int R, C; scanf("%d %d", &C, &R);
    int sanggeun_size = 0, fire_size = 0;
    // input을 처리
    for (int row = 0; row < R; row++)
        for (int col = 0; col < C; col++) {
            sanggeun_depth[row][col] = fire_depth[row][col] = -1;
            scanf(" %c", &map[row][col]);

            if (map[row][col] == '@') {
                sanggeun_queue.push({ row , col });
                sanggeun_size++;
                sanggeun_depth[row][col] = 0;
            }
            else if (map[row][col] == '*') {
                fire_queue.push({ row , col });
                fire_size++;
                fire_depth[row][col] = 0;
            }
        }

    // 불 먼저
    int depth = 1;
    while (sanggeun_size) {
        // 불 갱신
        while (fire_size) {
            fire_size--;
            pair<int, int> this_fire = fire_queue.front(); fire_queue.pop();
            for (int side_idx = 0; side_idx < SIDE; side_idx++) {
                int new_row = this_fire.first + side_arr[side_idx][0];
                int new_col = this_fire.second + side_arr[side_idx][1];

                // 인덱스 체크
                if (new_row < 0 || new_row >= R) continue;
                if (new_col < 0 || new_col >= C) continue;
                if (map[new_row][new_col] == '#') continue; // 벽 체크
                if (fire_depth[new_row][new_col] >= 0) continue; // 이전 단계 불 체크
                fire_depth[new_row][new_col] = depth;
                fire_queue.push({ new_row, new_col });
            }
        }

        // 상근 갱신
        while (sanggeun_size) {
            sanggeun_size--;
            pair<int, int> this_sanggeun = sanggeun_queue.front(); sanggeun_queue.pop();
            // 이전 단계에서 불이 넘친 구역이라면 그냥 넘긴다.
            if (0 <= fire_depth[this_sanggeun.first][this_sanggeun.second]
                && fire_depth[this_sanggeun.first][this_sanggeun.second] < depth) continue;

            for (int side_idx = 0; side_idx < SIDE; side_idx++) {
                int new_row = this_sanggeun.first + side_arr[side_idx][0];
                int new_col = this_sanggeun.second + side_arr[side_idx][1];

                // 인덱스 체크 == 정답
                if (new_row < 0 || new_row >= R || new_col < 0 || new_col >= C) {
                    return depth;
                }

                if (map[new_row][new_col] == '#') continue; // 벽 체크
                if (0 <= fire_depth[new_row][new_col]
                    && fire_depth[new_row][new_col] < depth) continue; // 이전 단계 불 체크
                if (sanggeun_depth[new_row][new_col] >= 0) continue; // 이전 상근 방문 여부 체크

                sanggeun_depth[new_row][new_col] = depth;
                sanggeun_queue.push({ new_row, new_col });
            }
        }

        if (sanggeun_size == 0) {
            sanggeun_size = sanggeun_queue.size();
            fire_size = fire_queue.size();
            depth++;
        }
    }
    return 0;
}

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int escape_flag = is_can_escape();
        if (escape_flag) printf("%d\n", escape_flag);
        else printf("IMPOSSIBLE\n");
    }
    return 0;
}




Search