[BOJ] 버스 갈아타기 BFS

2536번 버스 갈아타기 : 골드 1

"""
n_vertical개의 수직선(vertical)
n_horizontal개의 수평선(horizontal)

가장 왼쪽 아래 : (1,1)
가장 오른쪽 위 : (n_vertical,n_horizontal)

도로망을 운행하는 버스 : k개
버스는 수평 or 수직으로만 이동
각 버스는 모든 교차점에서 정차

출발지와 목적지의 서로 다른 교차점이 주어질 때
이용하는 버스의 최소 수

배열 이용하면 메모리 초과



"""

import sys
input = sys.stdin.readline

from collections import deque

n_vertical, n_horizontal = list(map(int, input().split()))

n_bus = int(input())

buses = [[] for _ in range(n_bus)]

for _ in range(n_bus):
    idx, x1, y1, x2, y2 = list(map(int, input().split()))
    buses[idx-1] = [x1,y1,x2,y2]

sx,sy,dx,dy = list(map(int, input().split())) # 출발지 x,y 목적지 x,y


start = deque() # 현재 탈수 있는 버스
s = set()
# sx, sy에서 탈 수 있는 버스
for i, bus in enumerate(buses):
    x1, y1, x2, y2 = bus
    if min(x1,x2) <= sx and max(x1, x2) >= sx and min(y1,y2) <= sy and max(y1, y2) >= sy:
        start.append((i, 1))
        s.add(i)

# 목적지를 포함하는 버스 노선 확인하기
target = set()
for i, bus in enumerate(buses):
    x1, y1, x2, y2 = bus
    if min(x1,x2) <= dx and max(x1, x2) >= dx and min(y1,y2) <= dy and max(y1, y2) >= dy:
        target.add(i)

def isTransfered(bus1, bus2):
    bus1 = buses[bus1]
    bus2 = buses[bus2]
    if max(bus1[0], bus1[2]) < min(bus2[0], bus2[2]) or min(bus1[0], bus1[2]) > max(bus2[0], bus2[2]):
        return False
    if max(bus1[1], bus1[3]) < min(bus2[1], bus2[3]) or min(bus1[1], bus1[3]) > max(bus2[1], bus2[3]):
        return False
    return True


answer = 1
visited = set(start)
if len(s&target) == 0:
    while True:
        cur, cnt = start.popleft()
        # print(cur, cnt)
        for i in range(n_bus):
            if i in visited:
                continue
            if isTransfered(i, cur):
                if i in target:
                    answer = cnt + 1
                    break
                start.append((i, cnt + 1))
                visited.add(i)

        if answer > 1:
            break
print(answer)

---

buses에는 각 idx에 맞는 bus를 넣어준다 -> 사실 그냥 .append로 넣어도 상관 없다.

buses = [[] for _ in range(n_bus)]

for _ in range(n_bus):
    idx, x1, y1, x2, y2 = list(map(int, input().split()))
    buses[idx-1] = [x1,y1,x2,y2]

start와 s는 시작점인 sx, sy 점에서 탑승 가능한 버스를 저장한다.
target은 목적지인 dx, dy점에서 탑승 가능한 버스를 저장한다.
target과 start 가 겹치는 원소를 가지는지(버스를 한 번만 타면 시작점에서 목적지로 이동 가능할 때)를 확인하기 위해 굳이 s를 따로 만드는 메모리 사치를 부렸다.

start = deque() # 현재 탈수 있는 버스
s = set()
# sx, sy에서 탈 수 있는 버스
for i, bus in enumerate(buses):
    x1, y1, x2, y2 = bus
    if min(x1,x2) <= sx and max(x1, x2) >= sx and min(y1,y2) <= sy and max(y1, y2) >= sy:
        start.append((i, 1))
        s.add(i)

# 목적지를 포함하는 버스 노선 확인하기
target = set()
for i, bus in enumerate(buses):
    x1, y1, x2, y2 = bus
    if min(x1,x2) <= dx and max(x1, x2) >= dx and min(y1,y2) <= dy and max(y1, y2) >= dy:
        target.add(i)

isTransfered 함수는 서로 다른 bus 두개의 index를 받아 각 bus가 서로 겹치는 정차점이 있는 지 확인한다.
bus1과 bus2의 x값 범위가 겹치지 않으면 두 버스는 절대 만나지 않는다
bus1과 bus2의 y값 범위가 겹치지 않으면 두 버스는 절대 만나지 않는다
-> 두 버스의 x값 범위와 y값 범위가 모두 겹치면 두 버스는 무조건 만난다

def isTransfered(bus1, bus2):
    bus1 = buses[bus1]
    bus2 = buses[bus2]
    if max(bus1[0], bus1[2]) < min(bus2[0], bus2[2]) or min(bus1[0], bus1[2]) > max(bus2[0], bus2[2]):
        return False
    if max(bus1[1], bus1[3]) < min(bus2[1], bus2[3]) or min(bus1[1], bus1[3]) > max(bus2[1], bus2[3]):
        return False
    return True

---

BFS를 통해 각 버스에서 탈 수 있는 모든 버스 노선을 탐색해줄 것이다.
시작점에서 탈 수 있는 노선과 목적지에서 탈 수 있는 노선이 겹친다면 (len(s&target) > 0), while 문을 돌지 않고 answer = 1을 반환한다.

isTransfered 함수로 현재 버스에서 탑승 가능한 버스를 탐색하고, 목적지에서 탈 수 있는 노선을 탑승 가능하다면 while 문을 멈춘다.

answer = 1
visited = set(start)
if len(s&target) == 0:
    while True:
        cur, cnt = start.popleft()
        # print(cur, cnt)
        for i in range(n_bus):
            if i in visited:
                continue
            if isTransfered(i, cur):
                if i in target:
                    answer = cnt + 1
                    break
                start.append((i, cnt + 1))
                visited.add(i)

        if answer > 1:
            break
print(answer)