Baekjoon 2536. 버스 갈아타기 / Python

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

알고리즘 설명

1. 입력 처리:
   • m, n: 격자의 크기(수직선의 수, 수평선의 수)를 입력받음.
   • k: 버스의 수를 입력받음.
   • 각 버스의 운행 구간을 입력받아 bus_line 리스트에 저장함.
   • 출발지와 목적지 좌표를 입력받아 bus_line에 추가함.
2. 교차 여부 확인:
   • cross(a, b) 함수는 두 버스 구간이 교차하는지 확인하여 교차하면 True, 그렇지 않으면 False를 반환함.
3. BFS 탐색:
   • visited 리스트는 각 버스의 방문 여부를 기록함.
   • q는 BFS를 위한 큐로, 초기값으로 출발지(-2)와 버스 수(0)를 넣음.
   • 큐가 빌 때까지 반복하면서, 현재 버스가 이미 방문한 경우 건너뜀.
   • 현재 버스를 방문 처리하고, 목적지에 도착한 경우 사용한 버스 수를 출력하고 종료함.
   • 모든 버스에 대해 교차 여부를 확인하고 교차하는 버스가 있으면 큐에 추가함.

from collections import deque as dq 
import sys 
input = sys.stdin.readline  

# 격자의 크기 m(수직선의 수), n(수평선의 수)을 입력
m, n = map(int, input().split())
k = int(input())  # 버스의 수를 입력

bus_line = []  # 각 버스의 운행구간을 저장할 리스트
for _ in range(k):
    tmp = list(map(int, input().split()))
    bus_line.append(tmp[1:])  # 버스의 운행구간만 저장 (버스 번호는 제외)

# 출발지와 목적지 좌표
sx, sy, dx, dy = map(int, input().split())

# 출발지와 목적지에 대한 가상의 버스를 추가
bus_line += [[sx, sy, sx, sy], [dx, dy, dx, dy]]

# 두 버스의 구간이 교차하는지 확인하는 함수
def cross(a, b):
    # 각 버스의 구간 좌표
    a1, b1, a2, b2, a3, b3, a4, b4 = *bus_line[a], *bus_line[b]
    # 두 구간이 교차하는지 확인
    return max(a1, a2) >= min(a3, a4) and max(a3, a4) >= min(a1, a2) and max(b1, b2) >= min(b3, b4) and max(b3, b4) >= min(b1, b2)

visited = [False] * (k + 2)  # 방문 여부를 저장할 리스트
q = dq([(-2, 0)])  # BFS를 위한 큐 초기화, (-2, 0)은 출발지에서 시작함을 의미

while q:
    current, cnt = q.popleft()  # 큐에서 현재 버스와 버스 수를 꺼냄
    if visited[current]:  # 이미 방문한 버스라면 건너뜀
        continue
    visited[current] = True  # 현재 버스를 방문함으로 표시
    if current == k + 1:  # 목적지에 도착했으면
        print(cnt - 1)  # 사용한 버스 수 출력 (시작을 0이 아닌 -2에서 시작했기 때문에 1을 뺌)
        break
    for tmp in range(k + 2):  # 모든 버스에 대해
        if not visited[tmp]:  # 아직 방문하지 않았다면
            if cross(current, tmp):  # 현재 버스와 교차하는지 확인
                q.append((tmp, cnt + 1))  # 교차하면 큐에 추가하고 버스 수를 증가시킴