백준-2644

BFS로 푸는 법

def bfs(a, b):
    q, visited = [a], [a]
    cnt = 0

    while q:
        size = len(q)
        for i in range(size):
            cur = q.pop(0)
            if cur == b:
                return cnt
            for j in d[cur]:
                if j not in visited:
                    visited.append(j)
                    q.append(j)
        cnt += 1
    return -1


n = int(input())
a, b = map(int, input().split())
t = int(input())
d = {i: [] for i in range(n + 1)}
for _ in range(t):
    x, y = map(int, input().split())
    d[x].append(y)
    d[y].append(x)


print(bfs(a, b))

DFS로 푸는 법 (스택사용)

n = int(input())
src, dest = map(int, input().split())
m = int(input())
graph = {i: [] for i in range(1, n + 1)}
for _ in range(m):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)

stk, visited, dist = [], [], 0
stk.append([src, dist])
check = False

while stk:
    node, dist = stk.pop()
    if dest == src:
        break
    if dest in graph[node]:
        check = True
        dist += 1
        break
    if node not in visited:
        visited.append(node)
        for elem in graph[node]:
            if elem not in visited:
                stk.append([elem, dist + 1])
if check == True:
    print(dist)
else:
    print(-1)

DFS로 푸는 법(재귀사용)

def dfs(graph, dest, count):
    visited[dest] = count

    for i in graph[dest]:
        if visited[i] == 0:
            dfs(graph, i, count + 1)


n = int(input())
start, end = map(int, input().split())
m = int(input())
graph = [[] for _ in range(n + 1)]

for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

visited = [0] * (n + 1)
count = 1

dfs(graph, end, count)
print(visited[start] - 1)