문제

문제 링크

해설

문제의 함정 - 동시성

• 코딩테스트 문제풀이에서 가장 까다로운 점 중 하나는 ‘동시성’ 구현입니다.
  • 예를 들어, 이 문제에서는 지훈이와 불이 같은 시간에 움직여야 합니다.
  • 하지만, 그 어떤 언어로도 코딩테스트에서는 ‘동시성’을 쉽게 구현할 수 없습니다.
  • 또한, ‘동시성’을 구현하도록 묻는 문제를 출제자가 내지도 않습니다.
• 절차지향적으로 작성되는 프로그램 언어상 어떻게든 지훈이 또는 불 둘 중 하나는 ‘먼저 이동’하게 됩니다. 그렇다면, 누가 먼저 이동하냐에 따라 같은 좌표라도 지훈이가 이동할 수 있는 좌표가 될 수도, 불가능한 좌표가 될 수도 있습니다.
• 바로 이 지점이 이 문제의 함정입니다. 이렇게 생각이 꼬리를 물게 되면 이 문제를 손도 댈 수 없게 됩니다.

문제의 변경 - 경쟁

• 문제의 한 문장을 아주 약간만 비틀어보면, 굉장히 간단해집니다.
  • ‘지훈이와 불은 매 분마다 한 칸씩 수평 또는 수직으로 이동한다’
  • ‘지훈이는 미로 A에서 매 분마다 한 칸씩 수평 또는 수직으로 이동한다.’
    ‘불은 미로 B에서 매 분마다 한 칸씩 수평 또는 수직으로 이동한다.’
• 지훈이와 불을 같은 구조를 가진 서로 다른 미로에서 이동시키는 것입니다.
• 이렇게 되면, 문제는 ‘탈출’에서 ‘경쟁’으로 바뀝니다.
  지훈이가 불보다 탈출구에 먼저 도착할 수 있다면, 지훈이는 탈출 할 수 있는 것입니다.
• 이때 임의의 좌표 (y, x)에 불이 먼저 도착할 수 있다면 지훈이는 그 좌표에 갈 수 없습니다.
• 그런 좌표를 피해가며 지훈이가 탈출구(미로의 가장자리)에 도착할 수 있다면, 지훈이는 탈출할 수 있습니다.

코드

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

constexpr int d[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

int R, C;
char maze[1000][1000];
int maze_person[1000][1000], maze_fire[1000][1000];

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    // 불이 없는 경우를 위한 예외처리가 필요. (★중요★)
    fill(&maze_fire[0][0], &maze_fire[0][0] + (1000 * 1000), 1e9);

    int sy, sx;                 // 지훈이 시작 위치
    queue<pair<int, int>> q;    // BFS를 위한 큐

    cin >> R >> C;
    for (int y = 0; y < R; y++) {
        for (int x = 0; x < C; x++) {
            cin >> maze[y][x];
            if (maze[y][x] == 'F') {
                maze_fire[y][x] = 1;
                q.emplace(y, x);
            } else if (maze[y][x] == 'J') {
                sy = y;
                sx = x;
            }
        }
    }

    // 불 이동 시작
    while (!q.empty()) {
        int cy = q.front().first, cx = q.front().second;
        q.pop();
        for (auto i : d) {
            int ny = cy + i[0], nx = cx + i[1];
            // 범위를 벗어난 인덱스 or 이미 불이 번진 곳 or 벽이 있는 곳이면 skip.
            if (ny < 0 || nx < 0 || ny >= R || nx >= C)             continue;
            if (maze_fire[ny][nx] != 1e9 || maze[ny][nx] == '#')    continue;
            maze_fire[ny][nx] = maze_fire[cy][cx] + 1;
            q.emplace(ny, nx);
        }
    }

    int answer = 0;

    // 지훈이 이동 시작
    maze_person[sy][sx] = 1;
    q.emplace(sy, sx);
    while (!q.empty()) {
        int cy = q.front().first, cx = q.front().second;
        q.pop();
        // 지훈이가 경계선에 도달했을 때 탈출 성공
        if (cy == R - 1 || cx == C - 1 || cy == 0 || cx == 0) {
            answer = maze_person[cy][cx];
            break;
        }
        for (auto i : d) {
            int ny = cy + i[0], nx = cx + i[1];
            // 범위를 벗어난 인덱스 or 이미 간 곳 or 벽이 있는 곳이면 skip.
            if (ny < 0 || nx < 0 || ny >= R || nx >= C)         continue;
            if (maze_person[ny][nx] || maze[ny][nx] == '#')     continue;
            // 지훈이는 해당 시간에 불이 번질 예정인 곳은 갈 수 없다.
            // 이 부분을 위해 'maze_fire 배열'을 1e9로 fill() 한 것.
            if (maze_fire[ny][nx] <= maze_person[cy][cx] + 1)   continue;
            maze_person[ny][nx] = maze_person[cy][cx] + 1;
            q.emplace(ny, nx);
        }
    }
    (answer) ? (cout << answer << '\n') : (cout << "IMPOSSIBLE \n");
    return 0;
}

소스코드 링크

• 아래에서 7번째 줄 if (maze_fire[ny][nx] <= maze_person[cy][cx] + 1) continue; 조건문이 이 문제의 핵심 코드입니다!
• 해당 좌표 (ny, nx)에 불이 먼저 올 수 있다면, 지훈이는 해당 좌표에 갈 수 없습니다.

결과