이번 문제는 깊이우선탐색을 통해 해결하였다. 구하고자 하는 두 사람의 번호를 입력 받고 한 사람의 번호부터 연결이 되어있는 모든 경우를 재귀 호출을 통해 검사하며 각각의 촌수를 구해주고 마지막에 반대편 사람의 촌수가 초기값 그대로라면 관계가 없는 것이므로 -1을 출력하고 반대편 사람의 촌수가 초기값이 아니라면 그 값을 출력해주는 방식으로 해결하였다.

• dfs함수를 cur을 인자를 갖도록 선언한다.
  -> visited[cur]을 True로 갱신한다.
  -> 만약 cur이 a2라면 함수를 종료한다.
  -> 1부터 n까지 반복하는 i에 대한 for문을 돌린다.
  --> 만약 relation[cur][i]가 1이고 visited[i]가 False일 경우,
  ---> cnt[i]를 cnt[cur]+1로 갱신한다.
  ---> dfs(i)를 재귀호출한다.
• n을 입력받는다.
• 방문처리에 사용할 리스트 visited를 False n+1개로 채운다.
• 촌수를 담을 리스트 cnt를 0 n+1개로 채운다.
• 두 사람의 번호 a1, a2를 입력받는다.
• m을 입력받는다.
• 관계를 저장할 리스트 relation을 선언하고 0을 (n+1)*(n+1)만큼 채운다.
• m번 반복하는 for문을 돌린다.
  -> x, y를 입력받는다.
  -> relation[x][y], relation[y][x]를 1로 갱신한다.
• dfs(a1)을 호출한다.
• 만약 cnt[a2]가 0일 경우 -1을 출력한다. (초기값인 경우)
• cnt[a2]가 0이 아닐 경우 cnt[a2]를 출력한다.

Code

def dfs(cur):
    visited[cur]=True
    if cur==a2:
        return
    for i in range(1, n+1):
        if relation[cur][i]==1 and visited[i]==False:
            cnt[i]=cnt[cur]+1
            dfs(i)

n=int(input())
visited=[False for _ in range(n+1)]
cnt=[0 for _ in range(n+1)]
a1, a2=map(int, input().split())
m=int(input())
relation=[[0]*(n+1) for _ in range(n+1)]
for _ in range(m):
    x, y=map(int, input().split())
    relation[x][y]=1
    relation[y][x]=1
dfs(a1)
if cnt[a2]==0:
    print(-1)
else:
    print(cnt[a2])