아직 ,, 나,, 쪼랩,,

1. 내 풀이: (아마도) 실패

import sys
input = sys.stdin.readline

n = int(input())
n1, n2 = map(int, input().split())
m = int(input())
graph = [[] for i in range(n+1)]
visited = [0] * (n+1)

for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
    
def dfs(k):
    visited[k] = 1
    for i in graph[k]:
        if i == n1:
            visited[i] = 1
            return
        if visited[i] == 0:
            visited[i] = 1
            dfs(i)

dfs(n2)
print(graph)
print(visited)
if visited[n1] == 1 and visited[n2] == 1:
    print(sum(visited)-1)
else:
    print(-1)

나름 고민해서 열심히 풀었는데 ...!
첫번째 테스트 케이스에서 7과 3의 촌수는 맞는데 3과 7로 순서를 바꾸면 촌수가 달라진다 ㅋㅋㅋ
곧바로 답 보기 ...

2. 다른 풀이

2-1. DFS

N = int(input())
A, B = map(int, input().split())
M = int(input())
graph = [[] for _ in range(N+1)]
visited = [False] * (N+1)
result = 0

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

# dfs
def dfs(v, num):
    global result  
    num += 1
    visited[v] = True

    if v == B:
        result += num

    for i in graph[v]:
        if not visited[i]:
            dfs(i, num)

dfs(A, 0)

if result == 0:
  print(-1)
else:
  print(result-1)

풀이 출처: https://wonyoung2257.tistory.com/56

풀이를 살짝 고쳤다!
result라는 변수를 처음에는 list로 선언하셨던데 코드를 보니 그럴 필요가 없는 것 같아서 global 변수로 선언했다.
물론 global 변수가 좋지 않은 건 사실이나, 코테에서 문제 없다고 하니까 ㅎㅎ ...

그래프 깊이가 깊어질 때 1을 더해준 풀이이다. 사실 깊어진다는 의미보다는 깊이가 변할 때가 더 맞는 것 같다! 왜냐하면 3, 7의 촌수를 구한다고 할 때 3 -> 1 -> 2 -> 7 의 순서로 가게 되는데 그래프를 그려보면은 1이 젤 head에 있기 때문이다.

2-2. BFS

from collections import deque

def bfs(node):
    queue = deque()
    queue.append(node)
    while queue:
        node = queue.popleft()
        for n in graph[node]:
            if check[n] == 0:
                check[n] = check[node]+1
                queue.append(n)
            
n = int(input())
graph = [[] for _ in range(n+1)]
s, e = map(int, input().split())
for _ in range(int(input())):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)
check = [0]*(n+1)
bfs(s)
print(check[e] if check[e] > 0 else -1)

풀이 출처: https://jinho-study.tistory.com/885

항상 느끼는 거지만 BFS로 풀든 DFS로 풀든, 개념은 똑같다.
대신 deque 혹은 재귀 함수로 구현하느냐의 차이랄까?
이런 문제 (무엇으로 풀든 상관없는 문제) 에서는 두 풀이 방법으로 모두 풀어보는 게 좋을 것 같다.

3. 마치며

그래프에 어느정도 익숙해지고는 있으나 여전히 풀이를 자유자재로 하기에는 미숙하다.
더 열심히 꾸준히 할 필요가 있다!