[백준24042/골드1] 횡단보도 - Python

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

 

횡단보도 프로젝트를 진행하면서 이런식으로 알고리즘을 짜면 좋겠다 싶은 생각을 했는데 비슷한 문제가 있어서 풀어봤다.

 

✅ 문제 조건

1. 교차로의 구역 : N개

2. 주어진 횡단보도의 전체 주기 : M분 (M개의 연결 노드, 1분간격으로 바뀜)

3. 0분에 출발해서 1번 구역에서 N번 구역까지 이동하는 최소 시간 구하기

 

 

✅ 접근 방식

일단 다른 다익스트라랑 똑같이 풀되, 가중치 계산이 따로 필요하다고 생각했다.

현재 시간, 현재 노드에서 이동할 수 있는 다른 연결 노드 중, 언제 출발할 수 있는지 (신호등이 언제 켜지는지) 계산이 필요했다.

 

알아야할 값

1. 연결된 노드 중 신호등이 켜지는 시간 (기다리는 시간)

2. 1에서 구한 기다리는 시간에서 현재시간과 이동시간(1분)을 더하여 다음 이동거리 구하기

 

기다리는 시간 구하기 : wait = ((다음 간선의 초록불 켜지는 시점)- (현재시각) % 주기M + 주기M) % 주기M

 

• 현재시각 % 주기M
  : 현재 시간이 M 주기 중 어디에 있는지 (예: 현재 시각 7이고 M=5면 7%5 = 2 → 현재 2분째 위치)
• (다음 간선의 초록불 켜지는 시점) - (현재시각) % 주기M
  : 현재 시간에서 다음 초록불까지 남은 시간
• + M 후 % M: 음수가 나올 경우를 보정해서 항상 0 이상 M 미만으로 만듦

 

 

 

✅ 구현

 

1. 횡단보도 정보 및 간선 정보 저장

N, M = map(int, input().split())
adjl = [[] for _ in range(N+1)]

for i in range(M):
    s, e = map(int, input().split())
    adjl[s].append((e, i)) # 출발 노드, 도착 노드, 초록불 시작 시간
    adjl[e].append((s, i))

 

2. 다익스트라 구현

dist = [float('inf')] * (N+1)
dist[1] = 0

heap = [(0, 1)] # 걸린 시간, 현재 노드

while heap:

    cur_t, cur_n = heappop(heap)

    if cur_n == N:
        print(cur_t)
        break

    if dist[cur_n] < cur_t:
        continue

    for next_n, green_start in adjl[cur_n]:

        # 현재 시점에서 이 간선이 언제 초록불이 되는지 계산
        wait = (green_start - cur_t % M + M) % M
        next_t = cur_t + wait + 1

        if dist[next_n] > next_t:
            dist[next_n] = next_t
            heappush(heap, (next_t, next_n))

 

✅ 정답 코드

'''
1. N개의 지역, M분의 횡단보도 주기 (1분마다 신호가 바뀜)
2. 이동하는 데 1분이 걸림
3. 0분에 시작해서 1번에서 N번까지 도착하는 최소 시간 출력
4. 계산 : 기본 다익스트라에서 현재 시점마다 초록불 켜지는 시간 구하여 가중치 계산하기
'''

import sys
input = sys.stdin.readline
from heapq import heappop, heappush

N, M = map(int, input().split())
adjl = [[] for _ in range(N+1)]

for i in range(M):
    s, e = map(int, input().split())
    adjl[s].append((e, i)) # 출발 노드, 도착 노드, 초록불 시작 시간
    adjl[e].append((s, i))

dist = [float('inf')] * (N+1)
dist[1] = 0

heap = [(0, 1)] # 걸린 시간, 현재 노드

while heap:

    cur_t, cur_n = heappop(heap)

    if cur_n == N:
        print(cur_t)
        break

    if dist[cur_n] < cur_t:
        continue

    for next_n, green_start in adjl[cur_n]:

        # 현재 시점에서 이 간선이 언제 초록불이 되는지 계산
        wait = (green_start - cur_t % M + M) % M
        next_t = cur_t + wait + 1

        if dist[next_n] > next_t:
            dist[next_n] = next_t
            heappush(heap, (next_t, next_n))

 

 

추억 회상하고 재밌는 문제였다