자료구조, 알고리즘/파이썬
[백준] 2644 - 촌수계산
heehminh
2024. 7. 12. 00:28
반응형
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)
반응형