백준 24042 - 횡단보도

문제 설명

당신은 집으로 가는 도중 복잡한 교차로를 만났다! 이 교차로에는 사람이 지나갈 수 있는 $N$ 개의 지역이 있고 그 지역 사이를 잇는 몇 개의 횡단보도가 있다. 모든 지역은 횡단보도를 통해 직, 간접적으로 연결되어 있다. 편의상 $N$ 개의 지역을 $1$부터 $N$까지로 번호를 붙이자.

당신은 이미 멀리서 교차로의 신호를 분석했기 때문에 횡단보도에 파란불이 들어오는 순서를 알고 있다. 횡단보도의 주기는 총 $M$ 분이며 $1$분마다 신호가 바뀐다. 각 주기의 $1+i (0 \le i < M)$ 번째 신호는 $i, M+i, 2M+i, 3M+i, \cdots$ 분에 시작해서 1$1$분 동안 Ai$A_i$번 지역과 Bi$B_i$번 지역을 잇는 횡단보도에 파란불이 들어오고, 다른 모든 횡단보도에는 빨간불이 들어온다. 한 주기 동안 같은 횡단보도에 파란불이 여러 번 들어올 수 있다.

횡단보도에 파란불이 들어오면 당신은 해당 횡단보도를 이용하여 반대편 지역으로 이동할 수 있으며 이동하는 데 $1$분이 걸린다. 횡단보도를 건너는 도중에 신호가 빨간불이 되면 안되기 때문에 신호가 $s \sim e$ 시간에 들어온다면 반드시 $s \sim e-1$ 시간에 횡단보도를 건너기 시작해야 한다.

횡단보도와 신호의 정보가 주어질 때, 시간 $0$분 에서 시작해서 $1$번 지역에서 $N$번 지역까지 가는 최소 시간을 구하는 프로그램을 작성하여라.

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, N개의 지역이 있고 M개의 횡단보도가 주어진다.

이때, M개의 횡단보도는 파란 불이 켜지는 시간이 i로 정해져있다.

1에서 출발하여 N에 도착할 때, 최소 시간을 구해야 한다.

 

해당 문제는 출발점과 도착점이 정해진 그래프 문제와 비슷하다.

하지만, 추가적인 조건이 하나 붙는다.

바로 이동할 수 있는 시간이다.

 

횡단보도에 파란 불이 켜져야 건널 수 있기 때문에 특정 지역에 아무리 빨리 도착하더라도 다음 지역까지 갈 수 있는 시간까지 기다려야 한다.

기다리는 시간은 주기에 맞추면 된다.

즉, 특정 지역에 도착해서 건널 수 있다면 건너고 이미 파란 불이 켜진 후라면 다음 시간이 올 때까지 기다리면 된다.

 

그렇다면 다음 불이 켜질 시간을 구하는 것이 핵심이 된다.

다음 불은 i + k * M시간에 켜지게 된다.

여기서 k는 주기가 몇 번 돌았는지 이다.

k는 현재 지역에 도착한 시간과 다음 지역으로 넘어갈 수 있는 시간만 있으면 구할 수 있다.

만약, 주기(M)가 12이고 A라는 지역에 14에 도착했다고 가정해 보자.

A에서 B로 넘어가는 파란 불이 켜지는 시간이 7이라고 한다면 이미 시간이 지난 후다.

그럼 다음 불이 켜질 때까지 기다려야 한다.

다음 불은 7 + 12 = 19에 켜지게 된다.

이는 현재 지역에 도착한 시간(14)에서 불이 켜지는 시간(7)을 뺀 것에서 주기를 나누면 몇 번의 사이클이 돌았는지 알 수 있다.

도착 시간 - 불이 켜지는 시간을 하는 것은 시작점을 해당 지역으로 옮기는 것과 같다.

즉, 시작점을 옮긴 뒤 몇 번의 주기를 돌았는지 확인하는 것이다.

만약, 도착 시간 - 불이 켜진 시간을 주기로 나눈 것이 나누어 떨어지지 않는다면 나머지만큼 더 진행됐다는 얘기이다.

따라서, 사이클에 1을 더해 주어야 한다.

long long cycle = (dist - nextDist) / M;
if ((dist - nextDist) % M != 0) cycle++;
passTime = cycle * M + nextDist;

해당 과정은 도착 시간이 불이 켜지는 시간보다 작을 때만 해주면 된다.

 

정리하자면, 다익스트라를 통해 1에서 N으로 가는 경로의 최소 시간을 구한다.

다음 지역으로 넘어가는 시간을 파란 불이 켜지는 시간에 맞도록 조정을 한다.

이때, 각 지역에 도착할 때, 최소 시간을 갱신한다.

---

 

 

 

 

 

전체 코드

#include <stdio.h>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cmath>
#include <climits>
#include <queue>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <list>
#include <bitset>

using namespace std;

int N, M;
vector<vector<pair<int, int>>> crosses;
vector<long long> Dist;

void dijk()
{
    priority_queue<pair<long long, int>> pq;
    pq.push({ 0, 1 });
    Dist[1] = 0;

    while (!pq.empty())
    {
        auto [dist, current] = pq.top();
        pq.pop();

        dist *= -1;

        for (auto& [next, nextDist] : crosses[current])
        {
            long long passTime = nextDist;
            if (nextDist < dist)
            {
                long long cycle = (dist - nextDist) / M;
                if ((dist - nextDist) % M != 0) cycle++;
                passTime = cycle * M + nextDist;
            }
                
            if (passTime < Dist[next])
            {
                Dist[next] = passTime;
                pq.push({ -Dist[next], next });
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cout.precision(4);

    cin >> N >> M;

    crosses.resize(N+1);
    Dist.resize(N+1, LLONG_MAX);

    for (int i = 1; i <= M; i++)
    {
        int a, b;
        cin >> a >> b;

        crosses[a].push_back({ b, i });
        crosses[b].push_back({ a, i });
    }

    dijk();
    cout << Dist[N];

    return 0;
}

---