2536 버스 갈아타기

from collections import deque

n, m = map(int, input().split())

k = int(input())

visit = [False] * (k + 1)
horizon_bus = []
vertical_bus = []
bus = [[0]]
isHorizon = [False] * (k + 1)
for _ in range(k):
    b, x1, y1, x2, y2 = list(map(int, input().split()))
    # 크기가 뒤죽박죽이라 오름차순으로 나열
    if x1 > x2:
        x2, x1 = x1, x2
    if y1 > y2:
        y2, y1 = y1, y2

    if x1 - x2:
        vertical_bus.append([b, y1, x1, x2])
    else:
        horizon_bus.append([b, x1, y1, y2])
        isHorizon[b] = True
    bus.append([b, x1, y1, x2, y2])

# 버스 번호가 무작위라 정렬
bus.sort(key=lambda x: x[0])
dest = list(map(int, input().split()))
start = dest[:2]
end = dest[2:]

queue = deque()
answer = 0
for index, y, x1, x2 in vertical_bus:
    # 시작지점과 y 가 같고 시작지점 x가 버스에 포함되어있으면 추가
    if start[1] == y and (x1 <= start[0] <= x2):
        queue.append([1, index, start[0], start[1]])
        visit[index] = True
for index, x, y1, y2 in horizon_bus:
    # 시작지점과 x 가 같고 시작지점 y가 버스에 포함되어있으면 추가
    if start[0] == x and (y1 <= start[1] <= y2):
        queue.append([1, index, start[0], start[1]])
        visit[index] = True


def solve():
    while queue:
        count, thisBus, thisX, thisY = queue.popleft()
        thisBusData = bus[thisBus]

        # 현재 버스에서 도착지점까지 갈 수 있는지 검증한다. 만약 갈수 있다면 현재까지의 버스 방문회수를 리턴하고 종료

        if isHorizon[thisBus]:
            if thisX == end[0] and thisBusData[2] <= end[1] <= thisBusData[4]:
                return count
        else:
            if thisY == end[1] and thisBusData[1] <= end[0] <= thisBusData[3]:
                return count

        # 다음 버스가 수평으로 가는 경우
        for nextBus, nextY, nextX1, nextX2 in vertical_bus:
            if visit[nextBus]:
                continue
            # 타고온 버스가 수직일 경우 교차점이 생기는지 조사한다.
            if isHorizon[thisBus]:
                if (nextX1 <= thisX <= nextX2) and (thisBusData[2] <= nextY <= thisBusData[4]):
                    queue.append([count + 1, nextBus, thisX, nextY])
                    visit[nextBus] = True
            # 같은 수평 수평일 경우 한 버스랑 다른 버스랑 겹치면 큐에 더하고 아예 다른 버스에 포함이 되는 버스면 추가하지 않는다.
            else:
                if thisY == nextY and ((thisBusData[3] <= nextX1) != (thisBusData[1] <= nextX2)):
                    queue.append([count + 1, nextBus, nextX1, thisY])
                    visit[nextBus] = True

        # 다음 버스가 수직으로 가는 경우
        for nextBus, nextX, nextY1, nextY2 in horizon_bus:
            if visit[nextBus]:
                continue
            # 타고온 버스가 수평일 경우 교차점이 생기는지 조사한다.

            if not isHorizon[thisBus]:
                if (nextY1 <= thisY <= nextY2) and (thisBusData[1] <= nextX <= thisBusData[3]):
                    queue.append([count + 1, nextBus, nextX, thisY])
                    visit[nextBus] = True

            # 같은 수직 수직일 경우 한 버스랑 다른 버스랑 겹치면 큐에 더하고 아예 다른 버스에 포함이 되는 버스면 추가하지 않는다.
            else:
                if thisX == nextX and ((thisBusData[4] <= nextY1) != (thisBusData[2] <= nextY2)):
                    queue.append([count + 1, nextBus, thisX, nextY1])
                    visit[nextBus] = True


print(solve())

먼저 처음 시작 지점에서 갈 수 있는 버스 노선들을 전부 큐에더가 저장을 한다.

버스 시작점과 종착점 사이에 시작 지점이 있으면 큐에다가 저장

이제 큐를 돌면서 순회를 하게 되는데

1. 지금 내가 탄 버스가 수평일 경우 :
   • 다음 버스가 수직일 경우 :
     두 선분을 비교해서 교차점이 생기는지 확인을 한다.
     교차점이 생기고 방문하지 않은 버스라면 큐에다가 저장
   • 다음 버스가 수평일 경우 :
     두 선분을 비교해서 겹치는 부분이 있는지 확인 한다.
     한 선분이 아예 다른 선분안에 포함되어 있으면 큐에 저장을 하지 않는다

지금 내가 탄 버스가 수직일 경우도 똑같이 수평 수직만 바꾸어서 똑같은 알고리즘으로 수행하면된다.

알고리즘 자체는 3분만에 떠올랐는데 코드 짜고 디버그 하느라 시간이 꽤 오래걸렸다.

대략 한 두시간 정도?