Easy is Perfect

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

  • melonicedlatte
  • Sep 17, 2018


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

불! 성공

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

문제

지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자!

미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야한다.

지훈이와 불은 매 분마다 한칸씩 수평또는 수직으로(비스듬하게 이동하지 않는다)  이동한다. 

불은 각 지점에서 네 방향으로 확산된다. 

지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다. 

지훈이와 불은 벽이 있는 공간은 통과하지 못한다.

입력

입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다.

다음 입력으로 R줄동안 각각의 미로 행이 주어진다.

 각각의 문자들은 다음을 뜻한다.

  • #: 벽
  • .: 지나갈 수 있는 공간
  • J: 지훈이의 미로에서의 초기위치 (지나갈 수 있는 공간)
  • F: 불이난 공간

J는 입력에서 하나만 주어진다.

출력

지훈이가 불이 도달하기 전에 미로를 탈출 할 수 없는경우 IMPOSSIBLE 을 출력한다.

지훈이가 미로를 탈출할 수 있는 경우에는 가장 빠른 탈출시간을 출력한다. 

예제 입력 1 

4 4
####
#JF#
#..#
#..#

예제 출력 1 

3

출처

Contest > Waterloo's local Programming Contests > 13 June, 2009 B번

알고리즘 분류

풀이

http://melonicedlatte.com/2018/09/17/021623.html 에 올라가 있는 백준 사이트의 3055 탈출이라는 문제와 굉장히 유사합니다. 

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

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

fire 큐에서 new_row와 new_col을 받은 다음에 인덱스 체크, 기존에 물이 차있었는지 여부, 비버 집인지, 돌인지를 체크합니다. 
jihoon 큐에서는 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 main() {
    char map[RC_MX][RC_MX] = { 0 };
    int jihoon_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>> jihoon_queue, fire_queue;
    int R, C; scanf("%d %d", &R, &C);
    int jihoon_size = 0, fire_size = 0;
    // input을 처리
    for (int row = 0; row < R; row++)
        for (int col = 0; col < C; col++){
            jihoon_depth[row][col] = fire_depth[row][col] = -1;
            scanf(" %c", &map[row][col]);

            if (map[row][col] == 'J') {
                jihoon_queue.push({ row , col });
                jihoon_size++;
                jihoon_depth[row][col] = 0;
            }
            else if (map[row][col] == 'F') {
                fire_queue.push({ row , col });
                fire_size++;
                fire_depth[row][col] = 0;
            }
        }

    // 불 먼저
    int depth = 1;
    while (jihoon_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(jihoon_size){
            jihoon_size--;
            pair<int, int> this_jihoon = jihoon_queue.front(); jihoon_queue.pop();
            // 이전 단계에서 불이 넘친 구역이라면 그냥 넘긴다.
            if (0 <= fire_depth[this_jihoon.first][this_jihoon.second]
                && fire_depth[this_jihoon.first][this_jihoon.second] < depth) continue;

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

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

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

                jihoon_depth[new_row][new_col] = depth;
                jihoon_queue.push({ new_row, new_col });
            }
        }

        if (jihoon_size == 0) {
            jihoon_size = jihoon_queue.size();
            fire_size = fire_queue.size();
            depth++;
        }
    }

    printf("IMPOSSIBLE");
    return 0;
}



Search