[Python] 2644 촌수 계산 - 실버2

문제

해당 문제 링크

정답 - BFS

from collections import deque

def bfs(v):
    q = deque()
    q.append(v)
    visited[v]=1

    while q:
        node=q.popleft()
        for i in range(1,n+1):
            if matrix[node][i]==1 and not visited[i]:
                q.append(i)
                res[i]=res[node]+1
                visited[i]=1

n=int(input())
x, y = map(int, input().split())

matrix=[[0]*(n+1) for _ in range(n+1)]
visited=[0]*(n+1)
res=[0]*(n+1)

k=int(input())
for i in range(k):
    a, b = map(int, input().split())
    matrix[a][b] = matrix[b][a] = 1

               
bfs(x)
if res[y]>0:
    print(res[y])
else:
    print(-1)

정답 - DFS

def dfs(v):
    visited[v]=1

    for i in range(1, n+1):
        if matrix[v][i]==1 and not visited[i]:
            res[i]=res[v]+1
            dfs(i)
            
n=int(input())
x, y = map(int, input().split())

matrix=[[0]*(n+1) for _ in range(n+1)]
visited=[0]*(n+1)
res=[0]*(n+1)

k=int(input())
for i in range(k):
    a, b = map(int, input().split())
    matrix[a][b] = matrix[b][a] = 1

               
dfs(x)
if res[y]>0:
    print(res[y])
else:
    print(-1)
    

풀이

입력 변수를 받고, 인접 영행렬을 생성하였다.
DFS와 BFS 게시물에서 작성한 것과 비슷하게 작성하여 구현을 했다.