[BOJ/Gold 3] 백준 26009 험난한 등굣길(C++)

문제 링크

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

26009번: 험난한 등굣길

 

 

문제

통학러 재헌이는 1교시 수업을 듣기 위해 아침 일찍 학교에 가려고 한다. 재헌이가 사는 지역은 크기가 N × M인 격자로 나타낼 수 있는데, i행 j열에 해당하는 칸을 (i, j)로 나타낼 때 재헌이는 현재 (1, 1)에, 학교는 (N, M)에 위치해 있다. 재헌이는 상하좌우로 한 칸씩 이동할 수 있고 지역 바깥으로 나갈 수는 없다.

등굣길은 순탄치만은 않은데, 이 지역에는 K개의 정체 구역이 있다. i번째 정체 구역은 세 정수 Ri, Ci, Di로 표현되며, 이는 (Ri, Ci)로부터 거리가 Di 이하인 칸들에는 극심한 교통 정체가 일어나고 있음을 의미한다. 두 칸 (R1, C1), (R2, C2)사이의 거리는 |R1 − R2| + |C1 − C2|와 같다.

재헌이는 교통 정체가 일어나고 있는 칸을 방문하면 수업에 지각하게 되며, 방문하지 않는다면 지각하지 않고 무사히 수업을 들을 수 있다. K개의 정체 구역에 대한 정보가 주어졌을 때 재헌이가 지각하지 않고 1교시 수업을 들을 수 있을지 알아보자. 또한 재헌이는 최대한 일찍 학교에 도착하려 하기 때문에, 만약 재헌이가 지각하지 않고 수업을 들을 수 있다면 최소 몇 번의 이동으로 수업을 들으러 갈 수 있는지도 구해보자.

입력

첫째 줄에 격자의 크기 N, M이 주어진다. (2 ≤ N, M ≤ 3,000)

다음 줄에 정체 구역의 수 K가 주어진다. (1 ≤ K ≤ 3,000)

다음 K개 줄에 걸쳐 각 정체 구역의 정보 Ri, Ci, Di가 주어진다. (1 ≤ Ri ≤ N, 1 ≤ Ci ≤ M, 0 ≤ Di ≤ 3,000)

 (1, 1) 또는 (N, M)에 교통 정체가 일어나고 있는 경우는 주어지지 않는다.

출력

재헌이가 지각하지 않고 수업을 들을 수 있으면 YES를 출력하고, 다음 줄에 최소 이동 횟수를 출력한다.

만약 지각하지 않고 수업을 들을 수 없다면 NO를 출력한다.

예제 입력 1

5 5
2
4 2 1
2 4 0

예제 출력 1

YES
8

재헌이가 초록색 화살표를 따라 이동한다면 지각하지 않고 수업을 들을 수 있으며, 이때 이동 횟수는 8$8$이다. 8$8$보다 적은 이동 횟수로 수업을 들으러 갈 수는 없다.

예제 입력 2

5 5
2
4 2 1
2 4 1

예제 출력 2

NO

예제 입력 3

4 7
3
1 3 0
1 3 1
4 5 1

예제 출력 3

YES
11

알고리즘 분류

• 그래프 탐색

풀이

우선 BFS를 수행하기 전에 갈 수 없는 지역부터 기록해야 하는데, 최대 3천 곳의 정체 구역을 기점으로 하여 BFS를 수행해야 할 것이다.

근데 특정 칸을 방문했다고 기록한다면, 교통 정체가 발생할 수 있는 다른 칸에 이동할 수 없는 경우가 나온다. 그런 경우가 없다고 해도 정체 구역이 최대 3천 곳이고, 격자는 3000 X 3000의 크기이며, D 또한 최대 3,000이기 때문에 시간 초과가 발생할 수 있다. 그렇다고 방문했다는 기록을 하지 않는다면 메모리 초과가 발생한다.

따라서, 정체 구역과 정체 구역을 중심으로 교통 정체가 발생할 수 있는 지역의 외곽 부분만을 기록해둔다면 시간을 크게 쓰지 않으면서 교통이 정체되는 곳이 어딘지를 파악할 수 있다.

교통 정체가 발생하는 곳들을 기억해둔 후에는 (1, 1)을 시작으로 BFS를 수행하여 (N, M)까지 도달하는 데 걸리는 최소의 시간을 구한다. 도달할 수 없다면 NO를 출력한다.

코드

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#define MAX 3001
#define INF 1e9
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int N, M, K;
int MAP[MAX][MAX];
bool Visited[MAX][MAX];
int MoveY[4] = { -1,0,1,0 };
int MoveX[4] = { 0,-1,0,1 };
int MoveR[4] = { -1,1,1,-1 };
int MoveC[4] = { 1,1,-1,-1 };
int Answer = INF;

void input() {
    cin >> N >> M;
    cin >> K;
    for (int i = 0; i < K; i++) {
        int R, C, D;
        cin >> R >> C >> D;
        MAP[R][C] = 1;
        int NowR = R;
        int NowC = C - D;
        for (int j = 0; j < 4; j++) {
            for (int k = 0; k < D; k++) {
                NowR += MoveR[j];
                NowC += MoveC[j];
                if ((NowR >= 1) && (NowR <= N) && (NowC >= 1) && (NowC <= M)) {
                    MAP[NowR][NowC] = 1;
                }
            }
        }
    }
}

void BFS() {
    queue<pair<pair<int, int>, int> > Q;
    Q.push(make_pair(make_pair(1, 1), 0));
    Visited[1][1] = true;

    while (!Q.empty()) {
        int NowY = Q.front().first.first;
        int NowX = Q.front().first.second;
        int NowT = Q.front().second;
        Q.pop();

        if ((NowY == N) && (NowX == M)) {
            Answer = min(Answer, NowT);
            continue;
        }

        for (int i = 0; i < 4; i++) {
            int NextY = NowY + MoveY[i];
            int NextX = NowX + MoveX[i];
            if ((NextY >= 1) && (NextY <= N) && (NextX >= 1) && (NextX <= M) && !Visited[NextY][NextX] && (MAP[NextY][NextX] != 1)) {
                Visited[NextY][NextX] = true;
                Q.push(make_pair(make_pair(NextY, NextX), NowT + 1));
            }
        }
    };
}

void settings() {
    BFS();
}

void find_Answer() {
    if (Answer == INF) {
        cout << "NO\n";
    }
    else {
        cout << "YES\n" << Answer << "\n";
    }
}

int main() {
    FASTIO
    input();
    settings();
    find_Answer();

    return 0;
}