[Python 3] BOJ - 2536 "버스 갈아타기"

 # 문제 링크

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

2536번: 버스 갈아타기

 

 # 풀이

 개인적으로 이 문제의 핵심은 그래프 모델링이라고 생각한다. n과 m에 비해 k가 5000으로 굉장히 작고, 문제에서 버스가 지나지 않는 곳에 출발점이 없기 때문에 다시 말해 버스까지 걸어갈 일이 없기 때문에 k만으로 문제를 풀 수 있다.

<그림 1. 예제 입력 1의 상태>

 위 그림은 예제 입력 1의 상태를 나타낸 것이다. 그런데 사실 그림 1에서 버스 1과 8은 생략되었다. 왜냐하면 버스 1은 버스 7에 의해 중복된 구간을 지나기 때문이고, 버스 8은 버스 5에 의해 중복된 구간을 지나기 때문이다. 즉, 현재 어떤 버스를 포함하는 다른 버스가 있다면 굳이 더 긴 버스 노선을 타지 않을 이유가 없다는 것이다. 그렇다면 여기서 어떻게 그래프 모델링을 할 수 있을까? 간단하다. 단 하나의 점이라도 겹치면 두 버스는 서로 인접하다고 놓는것이다. 예를 들어 현재 버스 7과 5는 인접하며, 버스 2와 버스 4는 인접하다.

<그림 2. 버스들의 다양한 위치 관계>

 위 그림 2는 버스들의 다양한 위치 관계를 나타낸 그림이다. 특징은 모두 한 점에서 만나고 있으며, 위 그림에 해당되는 두 버스 쌍은 인접하다고 할 수 있다.

<그림 3. 예제 입력의 최종 그래프 모델링>

 위 그림은 예제 입력의 그래프 모델링의 모습이다. 출발점이 속하는 버스인 2와 7, 도착점이 속하는 버스인 6의 최소 거리를 구하면 정답을 찾을 수 있다. 이 때 우리의 그래프 모델링의 간선의 가중치가 1이므로 최단 거리를 찾으려면 BFS가 필수적이다. 그런데 출발점이 속하는 버스가 2개이상일 수도 있으므로 시작 버스를 큐에 다같이 넣어줘야 한다

<그림 4. 코너 케이스>

 그런데 사실 이렇게 하면 정답을 구할 수 없다. 왜냐하면 그림 4와 같은 예외가 있기 때문이다. 아까 우리는 그림 2에서 '한 점'에서만 만나는 경우만 고려했다. 그런데 사실 그림 4와 같이 겹치게 만나도 충분히 갈아탈 수 있기 때문에 인접하다고 봐야 한다. 따라서 그림 4의 경우를 추가해주면 정답을 구할 수 있다 

 

 # 코드

import sys, collections

# 입력부
n, m = map(int, sys.stdin.readline().split())
k = int(sys.stdin.readline())

# arr : 버스의 시점과 종점을 저장하는 리스트
arr = [0] * (k + 1)

# adj : 인접 리스트
adj = [[] for _ in range(k + 1)]

# 버스 정보 입력
for _ in range(k):
    a,b,c,d,e = map(int, sys.stdin.readline().split())
    arr[a] = (min(b,d), min(c,e), max(b,d), max(c,e))
    
# check : 더 큰 버스에 의해 포함되는 버스 확인용 리스트
check = [False] * (k + 1)
for i in range(1, k + 1):
    temp = False
    x1, y1, x2, y2 = arr[i]
    for j in range(1, k + 1):
        if i == j:
            continue
        x3, y3, x4, y4 = arr[j]
        # 수직 버스인 경우
        if x1 == x2 == x3 == x4:
            if y3 <= y1 <= y2 <= y4:
                temp = True
        # 수평 버스인 경우
        if y1 == y2 == y3 == y4:
            if x3 <= x1 <= x2 <= x4:
                temp = True
    check[i] = temp

for i in range(1, k + 1):
    # 이미 포함되는 버스면 continue
    if check[i]:
        continue
    x1, y1, x2, y2 = arr[i]
    for j in range(1, k + 1):
        # 이미 포함되는 버스면 continue
        if check[j]:
            continue
        if i == j:
            continue
        x3, y3, x4, y4 = arr[j]
        # 한 점에서 만나는 경우 (방향이 서로 다른 경우)
        if x1 <= x3 <= x2 and x1 <= x3 <= x2:
            if y3 <= y1 <= y4 and y3 <= y2 <= y4:
                adj[i].append(j)
                adj[j].append(i)
        # 한 점 혹은 겹치는 경우 (수평 방향)
        if y1 == y2 == y3 == y4:
            if not (x1 > x4 or x2 < x3):
                adj[i].append(j)
                adj[j].append(i)
        # 한 점 혹은 겹치는 경우 (수직 방향)
        if x1 == x2 == x3 == x4:
            if not (y1 > y4 or y2 < y3):
                adj[i].append(j)
                adj[j].append(i)

# 시작점, 도착점 입력부
sx, sy, ex, ey = map(int, sys.stdin.readline().split())

# start : 시작점이 속하는 버스 번호 리스트
start = []

# end : 도착점이 속하는 버스 번호 리스트
end = []
for i in range(1, k + 1):
    if check[i]:
        continue
    x1, y1, x2, y2 = arr[i]
    if x1 <= sx <= x2 and y1 <= sy <= y2:
        start.append(i)
    if x1 <= ex <= x2 and y1 <= ey <= y2:
        end.append(i)

# BFS
q = collections.deque()
vis = [-1] * (k + 1)
for i in start:
    q.append(i)
    vis[i] = 0
while q:
    now = q.popleft()
    for next in adj[now]:
        if vis[next] == -1:
            vis[next] = vis[now] + 1
            q.append(next)
            
# 정답 출력
ans = 9876543210
for i in end:
    ans = min(ans, vis[i])
print(ans + 1)