[Algorithm/Python][백준] 2644번 촌수계산

[BOJ] 2644번 촌수계산

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

- 문제 접근

• 이 문제는 DFS와 BFS 두가지 방법 모두로 풀어보았다
• 이 문제는 DFS가 간단해서 더 나은것같다
• 전에 2차원 배열로 푸는게 나을 것 같다고 하는데 다시 정정한다. 이 코드처럼 연결리스트로 푸는게 훨씬 나은 것 같다!
• 끊어져있는 그래프일 때는 어떻게 푸는가 관련 문제도 한번 풀어봐야겠다.

- 내 코드

from collections import deque

def bfs(start):
    queue = deque([start])
    visited[start]=True
    while queue:
        v = queue.popleft()
        for i in graph[v]:
            if visited[i]==False:
                queue.append(i)
                check[i]=check[v]+1
                visited[i]=True

def dfs(V):
    visited[V] = True
    for i in graph[V]:
        if visited[i]==False:
            check[i]=check[V]+1
            dfs(i)

N = int(input())

A, B = map(int, input().split())

M = int(input())

graph = [[] for row in range(N+1)]

for i in range(M):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)

visited = [False] * (N+1)
check=[0]*(N+1)

# bfs(A)
dfs(A)

if check[B]>0:
    print(check[B])
else:
    print(-1)