[Baekjoon(백준)][4179번] 불!(C++)

안녕하세요! 오늘은 코딩테스트 문제 중 하나인 "불!" 문제를 해결하는 방법에 대해 설명하려고 합니다. 미로에서의 지훈이의 위치와 불이 난 위치를 고려하여 지훈이가 불에 타기 전에 탈출할 수 있는지 여부와 가장 빠른 탈출 시간을 구하는 문제입니다. 문제를 해결하는 과정과 코드를 자세히 알아보겠습니다.

문제링크:

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

4179번: 불!

문제 개요

미로에서 지훈이가 불을 피해 탈출해야 하는 상황입니다. 미로의 각 위치는 벽(#), 빈 공간(.), 지훈이의 초기 위치(J), 불(F)로 구성됩니다. 지훈이와 불은 각각 매 분마다 상하좌우로 한 칸씩 이동할 수 있으며, 지훈이는 미로의 가장자리로 이동하여 탈출할 수 있습니다. 불은 빈 공간으로만 확산되며, 지훈이는 불이 도달하기 전에 해당 위치로 이동할 수 있어야 합니다.

해결 전략

이 문제는 BFS(너비 우선 탐색) 알고리즘을 사용하여 불의 확산과 지훈이의 이동을 모두 계산해야 합니다. 불이 먼저 확산되고, 그 다음 지훈이가 이동하는 순서로 진행합니다. 지훈이가 미로의 가장자리에 도달하면 탈출이 가능합니다.

코드 구현

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

// 전역 변수 선언
int r, c; // 미로의 행과 열 크기
char maps[1005][1005]; // 미로 정보 저장 배열
int fire[1005][1005]; // 불이 퍼지는 시간 저장 배열
int person[1005][1005]; // 지훈이 이동 시간 저장 배열

// 방향 벡터 (상, 하, 좌, 우)
int dy[] = { -1,0,1,0 };
int dx[] = { 0,1,0,-1 };

pair<int, int> start_J; // 지훈이의 시작 위치
int ret; // 결과값 (탈출 시간)

// 불 확산 처리 함수
void bfs(int y, int x) {
    // 방문 배열 초기화
    fill(&fire[0][0], &fire[0][0] + 1005 * 1005, -1);
    queue<pair<int, int>> s;
    for (int y = 0; y < r; y++) {
        string temp = "";
        cin >> temp;
        for (int x = 0; x < temp.size(); x++) {
            maps[y][x] = temp[x];
            if (maps[y][x] == 'J') start_J = {y, x}; // 지훈이 위치 저장
            if (maps[y][x] == 'F') { // 불의 위치에서 BFS 시작
                fire[y][x] = 1;
                s.push({y, x});
            }
        }
    }
    // 불 BFS 처리
    while (!s.empty()) {
        pair<int, int> cur = s.front();
        s.pop();
        for (int i = 0; i < 4; i++) {
            int ny = cur.first + dy[i];
            int nx = cur.second + dx[i];
            // 불 확산 조건 검사 및 처리
            if (ny >= 0 && ny < r && nx >= 0 && nx < c && maps[ny][nx] != '#' && fire[ny][nx] == -1) {
                fire[ny][nx] = fire[cur.first][cur.second] + 1;
                s.push({ny, nx});
            }
        }
    }
    // 지훈이 BFS 처리
    person[start_J.first][start_J.second] = 1;
    s.push(start_J);
    while (!s.empty()) {
        pair<int, int> cur = s.front();
        s.pop();
        // 탈출 조건 검사 및 처리
        if (cur.first == 0 || cur.second == 0 || cur.first == r-1 || cur.second == c-1) {
            ret = person[cur.first][cur.second];
            break;
        }
        // 지훈이 이동 가능 조건 검사 및 처리
        for (int i = 0; i < 4; i++) {
            int ny = cur.first + dy[i];
            int nx = cur.second + dx[i];
            if (ny >= 0 && nx >= 0 && ny < r && nx < c && maps[ny][nx] != '#' && !person[ny][nx] && (fire[ny][nx] == -1 || fire[ny][nx] > person[cur.first][cur.second] + 1)) {
                person[ny][nx] = person[cur.first][cur.second] + 1;
                s.push({ny, nx});
            }
        }
    }
    // 결과 출력
    if (ret != 0) cout << ret << "\n"; // 탈출 가능한 경우
    else cout << "IMPOSSIBLE \n"; // 탈출 불가능한 경우
}

코드 설명

• 변수 선언: maps 배열에 미로의 상태를 저장하고, fire와 person 배열에 각각 불과 지훈이가 해당 위치에 도달하는 시간을 저장합니다.
• 불 BFS 처리: 불의 위치에서 시작하여 빈 공간으로 확산되는 시간을 fire 배열에 기록합니다.
• 지훈이 BFS 처리: 지훈이의 위치에서 시작하여 불이 도달하기 전에 이동할 수 있는 경로를 탐색하고, 탈출 시간을 person 배열에 기록합니다.
• 탈출 여부 판단: 지훈이가 미로 가장자리에 도달할 수 있으면 탈출 성공, 도달할 수 없으면 "IMPOSSIBLE" 출력.

결론

이 문제는 BFS 알고리즘을 사용하여 불의 확산과 지훈이의 이동을 모델링하는 방식으로 해결할 수 있습니다. 각 단계에서 조건에 맞는 처리를 통해 최종적으로 지훈이가 탈출할 수 있는지 여부와 필요한 최소 시간을 계산할 수 있습니다.