[백준 2536번] 버스 갈아타기 (Python3)

import sys,collections
input = sys.stdin.readline

def cross(i,j):
  x1,y1,x2,y2,x3,y3,x4,y4 = *line[i],*line[j]
  return max(x1,x2)>=min(x3,x4) and max(x3,x4)>=min(x1,x2) and max(y1,y2)>=min(y3,y4) and max(y3,y4)>=min(y1,y2)

M,N = map(int,input().split())
K = int(input())

line = [[*map(int,input().split())][1:] for i in range(K)]
sx,sy,dx,dy = map(int,input().split())
line += [[sx,sy,sx,sy],[dx,dy,dx,dy]]

visited = [0]*(K+2)
dq = collections.deque([(-2,0)])
while dq:
  now,d = dq.popleft()
  if visited[now]:
    continue
  visited[now] = 1
  if now == K+1:
    print(d-1)
    break
  for next in range(K+2):
    if not visited[next]:
      if cross(now,next):
        dq.append((next,d+1))

선분교차 + BFS를 이용하여 해결하였다.

뱀 [백준 10875번] 뱀 (Python3) (tistory.com) 문제와 결이 비슷하다. 좌표의 크기가 매우 크기 때문에, 상하좌우 이동으로 BFS해서는 절대 해결할 수 없다.

 

알고리즘을 설명하면,

1. 각 버스 노선의 양 끝점을 저장, 시작지점과 도착지점도 선분처럼 저장한다.

2. 시작지점부터 BFS, 이때 현재 노선과 crossed한 노선에 대해서만 탐색을 한다.

3. 최종 목적지에 도착하면 개수 출력

 

참고로 파이썬으로 풀면 한층 더 어려운 문제이다. 풀이가 약간만 더러워져도 메모리 제한과 시간제한의 늪에서 빠져나오기 쉽지 않다.

 

 

오늘의 교훈) 다른 언어를 공부하는것도 고려해보자