[백준 2644번] 촌수계산 - python

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

📌 문제 탐색하기

목표

• 주어진 두 사람의 촌수를 계산하는 프로그램을 작성해보자.
• 즉, 사람들 간의 관계가 주어졌을 때 서로 얼마나 많이 떨어져있는지 계산해서 반환하는 문제이다.

입력값

• 첫째 줄에 전체 사람수 n이 주어진다. (1 ≤ n ≤ 100)
• 둘째 줄에 얼마나 많이 떨어져있는지 계산해야하는 두 사람의 번호가 주어진다.
• 셋째 줄에는 부모 자식들 간의 관계의 개수 m이 주어진다. 부모 자식간의 관계이므로 해당 문제에서 사이클은 없다고 판단할 수 있다.
• 넷째 줄부터 부모 자식간의 관계를 나타내는 번호 x, y가 주어진다. 이때, x가 부모, y가 자식이다.
• ex)

9
7 3
7
1 2
1 3
2 7
2 8
2 9
4 5
4 6

출력값

• 두 사람의 촌수를 나타내는 정수를 출력한다. 친척 관계가 전혀 없는 두 사람이라면 -1을 출력한다.
• ex)
• 3

📌 코드 설계하기

해결 아이디어

• 어제의 문제와 살짝 달라진 부분을 찾을 수 있다. 어제까지만 해도 사이클이 존재했고 내부의 개수를 카운팅한다기보다는 사이클의 개수에 초점을 두고 있었다. 이제는 내부 정점 사이의 관계를 파악해야하므로 dfs 내부에서 계산이 이루어져야겠다는 생각을 했다.
• 처음에는 부모를 인덱스 값이라고 생각하고 자식을 해당 부모 인덱스 값 밑에 삽입하는 것이 좋겠다는 생각을 했다. 하지만 그렇게 진행을 했을 때 다시 되돌아오기가 복잡하다는 생각을 들었다. 즉, 부모 1번에 자식 3번이 있었는데 자식 3번이 자식 5번만 가지고 있더라면 그리고 만약 5번은 관련이 없는 사람이면 다시 부모 1번으로 돌아와서 다른 곳을 탐색해야한다. 따라서 서로 이어져 있는 각 인덱스는 자신과 연결되어있는 사람 모두를 저장할 수 있도록 해야한다.

📌 정답 코드

import sys

def dfs(n, cnt):
    visited[n] = True
    cnt += 1
    if b in arr[n]:
        return cnt
    for i in range(len(arr[n])):
        if b== arr[n][i]:
            return cnt
        if not visited[arr[n][i]]:
            res = dfs(arr[n][i], cnt)
            if res != -1:
                return res
    return -1

n = int(sys.stdin.readline())
a, b = map(int, sys.stdin.readline().split())
m = int(sys.stdin.readline())
cnt = 0
arr = [[] for i in range(n+1)]
visited = [False] * (n+1)
for i in range(m):
    x, y = map(int, sys.stdin.readline().split())
    arr[x].append(y)
    arr[y].append(x)
print(dfs(a, cnt))

시간 복잡도 구해보기

• 입력
  • 총 n번 입력을 진행한다. → O(N)
• DFS 탐색
  • 각 정점은 한 번만 방문한다. (visited 덕분에) → O(n)
  • 각 간선은 양쪽에서 한 번씩 확인한다. → O(m)

최종 시간 복잡도: O(N+M)

📌 다른 풀이

import sys

def dfs(n, cnt):
    if b == n:
        return cnt
    visited[n] = True
    for i in (arr[n]):
        if not visited[i]:
            res = dfs(i, cnt+1)
            if res != -1:
                return res
    return -1

n = int(sys.stdin.readline())
a, b = map(int, sys.stdin.readline().split())
m = int(sys.stdin.readline())
cnt = 0
arr = [[] for i in range(n+1)]
visited = [False] * (n+1)
for i in range(m):
    x, y = map(int, sys.stdin.readline().split())
    arr[x].append(y)
    arr[y].append(x)
print(arr)
print(dfs(a, cnt))

위의 코드를 정리한 버전이다. 처음 풀 때는 이것저것 조건을 넣고 하느라 중복된 조건도 있고 좀 더 장황한 코드들이 있었다. for문을 간단하게 줄여서 list에 있는 값들을 바로 뽑을 수 있도록 하였고 중복된 b==n일 때의 로직을 정리하여 처음 조건문으로 넣어줬다.

사실상 이 문제는 BFS로 풀었을 때 더 직관적이었다.

import sys
from collections import deque

n = int(sys.stdin.readline())
a, b = map(int, sys.stdin.readline().split())
m = int(sys.stdin.readline())

adj = [[] for _ in range(n + 1)]
for i in range(m):
    x, y = map(int, sys.stdin.readline().split())
    arr[x].append(y)
    arr[y].append(x)

def bfs(start, target):
    dist = [-1] * (n + 1)
    q = deque([start])
    dist[start] = 0
    while q:
        u = q.popleft()
        if u == target:
            return dist[u]
        for v in adj[u]:
            if dist[v] == -1:
                dist[v] = dist[u] + 1
                q.append(v)
    return -1

print(bfs(a, b))

u와 연결된 모든 이웃 v를 확인하면서 아직 방문하지 않았다면 촌수는 부모의 촌수에 1을 더하고 큐에 추가하며 확인한다.