DFS - 촌수계산 [2644번]

DFS 와 BFS로 풀이해보았다.

 

DFS

def dfs(p, cnt):
    global chk
    if p == c:
        chk = True
        print(cnt)
        return
    
    for i in range(101):
        if graph[p][i] == 1 and visited[i] == False:
            visited[i] = True
            dfs(i, cnt + 1)
            visited[i] = False

n = int(input())
p, c = map(int, input().split())
m = int(input())
graph = [[0]*(101) for _ in range(101)]
for i in range(m):
    x, y = map(int, input().split())
    graph[x][y] = 1
    graph[y][x] = 1

visited = [False] * 101
visited[p] = True

chk = False

dfs(p, 0)

if chk == False:
    print(-1)

 

BFS

from collections import deque

def bfs(p):
    global c
    q = deque([p])
    while q:
        x = q.popleft()
        if x == c:
            print(visited[x])
            return 
        
        for y in range(len(graph[x])):
            if graph[x][y] == 1 and not visited[y]:
                q.append(y)
                visited[y] = visited[x]+ 1
                
    print(-1)
    return
                
n = int(input())
p, c = map(int, input().split())
m = int(input())
graph = [[0]*(101) for _ in range(101)]
for i in range(m):
    x, y = map(int, input().split())
    graph[x][y] = 1
    graph[y][x] = 1
    
visited = [0] * 101
bfs(p)