[백준] 2644 - 촌수계산

https://www.acmicpc.net/problem/2644

 

 

알고리즘

DFS, BFS 

 

풀이 

N: 정점의 개수

x, y: 촌수를 계산해야 하는 서로 다른 두 사람의 번호 

M: 간선의 종류 

 

 

같은 연결요소내에 속한 정점의 경우에는 간선의 개수를 세면 되고

같은 연결요소가 아니라면 -1을 출력하면 된다.

7, 3의 경우에는 7, 2, 1, 3을 거쳐야 하므로 아래 코드에서 횟수는 4가 된다. 자기 자신은 빼야하므로 -1을 해주어 답은 3

 

이 문제는 출력 과정에서 1번 틀렸는데,

처음에는 res = 0 으로 선언해두고, res가 0이라면 -1 출력 아니라면 res 출력으로 짰더니, 

res가 0이 아닌 경우 -1과 res값 모두가 출력되었다.

 

그래서 res를 빈 배열로 만들어두고, 배열의 길이가 0인 경우 아닌 경우로 나누어 출력했다. 

 

전체 코드

# 촌수계산

N = int(input())
x, y = map(int, input().split())
M = int(input())

adj = [[0]*(N+1) for _ in range(N+1)]

for _ in range(M):
    u, v = map(int, input().split())
    adj[u][v] = adj[v][u] = 1
    
chk = [False] * (N+1)
res = []

def dfs(now, ans):
    chk[now] = True 
    
    if now == y:
        res.append(ans+1)
        return 
    
    for nxt in range(N+1):
        if adj[now][nxt] and not chk[nxt]:
            chk[nxt] = True 
            dfs(nxt, ans+1)
    
dfs(x, 0)

if res:
    print(res.pop()-1)
else:
    print(-1)