[백준 🥇4] 1976번 여행 가자 (Python/파이썬)

1️⃣ 문제

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

2️⃣ 코드

보통 풀이 검색해보면 유니온파인드로 많이 풀었던데 나는 BFS로 풀었다
여행 계획이 1 2 3 일 때 1→2, 2→3으로 갈 수 있는지 각각 BFS로 확인하는 방식으로 풀었음
즉, m-1번 BFS로 탐색한다

from collections import deque

n = int(input())
m = int(input())

city = []

for i in range(n):
    city.append(list(map(int, input().split())))
plan = list(map(int, input().split()))

def bfs(s, e):
    q = deque()
    q.append(s)
    visited = [False] * n
    visited[s] = True

    while q:
        here = q.popleft()

        if here == e:
            return True

        for i in range(n):
            if city[here][i] == 1 and not visited[i]:
                visited[i] = True
                q.append(i)

    return False

answer = True
for i in range(m-1):
    if plan[i] != plan[i+1]:
        if not bfs(plan[i]-1, plan[i+1]-1):
            answer = False
            break

if answer:
    print('YES')
else:
    print('NO')

사실 BFS 함수에서 city[here][i]로 써야하는데 city[v][i]로 잘못 써서 1시간 삽질했기 때문에 억울해서 쓰는 게시글😔