[파이썬] 백준 2021 : 최소 환승 경로 (골드2)

[파이썬] 백준 2021 : 최소 환승 경로 (골드2)

2021번: 최소 환승 경로

---

문제

---

풀이

0. 방향성 생각

• 필요한 노드는 환승역, 출발점, 시작점이다.
• 지나는 역의 개수가 2개 이상인 점과 출발점, 시작점만을 추출한다.
• BFS를 통해 탐색하고, 이동하면서 노선이 바뀌면 체크해주기

1. 입력

from collections import deque,defaultdict
import sys
input = lambda : sys.stdin.readline().rstrip()

n,l = map(int,input().split())
table = {i:0 for i in range(1,n+1)}
lines = [[] for _ in range(l+1)]
for line in range(1,l+1): 
    lines[line].extend(list(map(int,input().split()))[:-1])
    for station in lines[line]:
        table[station] += 1
start,end = map(int,input().split())

• table 딕셔너리를 만들어서 지하철 라인이 지나갈 때 마다 +1을 해준다.

2. 필요한 노드만 추출

new_lines = [[] for _ in range(l+1)]
for line in range(1,l+1):
    for station in lines[line]:
        if table[station] > 1 or station == start or station == end:
            new_lines[line].append(station)

• 환승역이랑 시작점, 끝점만 추출한다.

3. graph 연결, 노선 연결정보 move 정의

move = defaultdict(int)
graph = [[] for _ in range(n+1)]
for line,new_line in enumerate(new_lines):
    count = len(new_line)
    if count > 1:
        for i in range(count-1):
            a,b = new_line[i],new_line[i+1]
            graph[a].append(b)
            graph[b].append(a)
            move[(a,b)] = line
            move[(b,a)] = line

• a,b로 가는 노선정보를 move에 추가한다.
• graph 연결요소를 추가한다.

4. BFS

inf = 1e6
visit = [inf]*(n+1)
visit[start] = 0
q = deque()
for nx in graph[start]:
    q.append((start,0,move[(start,nx)]))

while q:
    x,t,line = q.popleft()
    if x == end:
        break

    if t > visit[x]:
        continue

    for nx in graph[x]:
        if move[(x,nx)] == line: nt = t
        else: nt = t+1

        if nt < visit[nx]:
            q.append((nx,nt,move[(x,nx)]))
            visit[nx] = nt

print(visit[end]) if visit[end] != inf else print(-1)

 

• 현재 타고있는 노선 line에서 다른 노선으로 변경될 때, 환승 카운트 t를 늘려준다.

---

전체코드

from collections import deque,defaultdict
import sys
input = lambda : sys.stdin.readline().rstrip()

n,l = map(int,input().split())
table = {i:0 for i in range(1,n+1)}
lines = [[] for _ in range(l+1)]
for line in range(1,l+1): 
    lines[line].extend(list(map(int,input().split()))[:-1])
    for station in lines[line]:
        table[station] += 1
start,end = map(int,input().split())

new_lines = [[] for _ in range(l+1)]
for line in range(1,l+1):
    for station in lines[line]:
        if table[station] > 1 or station == start or station == end:
            new_lines[line].append(station)

move = defaultdict(int)
graph = [[] for _ in range(n+1)]
for line,new_line in enumerate(new_lines):
    count = len(new_line)
    if count > 1:
        for i in range(count-1):
            a,b = new_line[i],new_line[i+1]
            graph[a].append(b)
            graph[b].append(a)
            move[(a,b)] = line
            move[(b,a)] = line

inf = 1e6
visit = [inf]*(n+1)
visit[start] = 0
q = deque()
for nx in graph[start]:
    q.append((start,0,move[(start,nx)]))

while q:
    x,t,line = q.popleft()
    if x == end:
        break

    if t > visit[x]:
        continue

    for nx in graph[x]:
        if move[(x,nx)] == line: nt = t
        else: nt = t+1

        if nt < visit[nx]:
            q.append((nx,nt,move[(x,nx)]))
            visit[nx] = nt

print(visit[end]) if visit[end] != inf else print(-1)

 

코멘트

풀고보니까 진짜 못푼듯. 변수할당도 쓸데없이 많이했고, 결과론적으로 다른 점들을 추출할 필요가 없었음.

저번에 풀었던 죽음의 비 문제에서 필요없는 노드들을 생각하지 않는 발상에서 접근.

그 때는 좌표 정보를 바로 맨하탄 거리로 치환해서 금방 얻을 수 있었다면, 이번에는 많은 데이터에 대해서 순회를 여러번 해버리니 시간이 오래걸렸다.

입력정보 보고 잘 생각해서 선택하기.