백준 2644번 촌수계산 Python 풀이

🕵️‍♂️ 문제 탐색

그래프와 DFS(깊이 우선 탐색)

• 그래프 표현:
  • 각 노드를 가족 구성원으로 보고, 간선을 통해 부모-자식 관계를 표현.
  • 무방향 그래프를 인접 리스트로 구현.
• DFS 탐색:
  • DFS를 사용해 두 사람 간의 촌수를 계산.
  • 탐색 과정에서 방문한 노드를 기록해 중복 탐색을 방지.
• 결과 처리:
  • DFS 탐색 중에 목표 노드 b에 도달하면 촌수를 기록.
  • b에 도달하지 못하면 연결되지 않았다고 간주하여 -1을 출력.

시간 복잡도 분석

1. 그래프 탐색:
   • 노드의 갯수 n, 간선의 갯수 m.
   • DFS는 각 노드와 간선을 한 번씩 방문하므로 시간 복잡도는 O(n+m).

---

🛠️ 코드 설계

그래프 생성

1. 인접 리스트:
   • 입력받은 관계를 인접 리스트로 저장.
   • 예를 들어, x→y는 graph[x].append(y)와 graph[y].append(x)로 처리.

DFS 탐색

1. 재귀적 탐색:
   • 현재 노드를 방문 처리하고, num을 증가시켜 촌수를 추적.
   • 목표 노드 b에 도달하면 촌수를 result 리스트에 저장.
2. 방문 체크:
   • 이미 방문한 노드는 다시 탐색하지 않도록 visited 배열을 활용.

---

💻 정답 코드

n = int(input())  # 전체 사람 수
a, b = map(int, input().split())  # 촌수를 계산할 두 사람
n_pair = int(input())  # 관계의 개수
graph = [[] for _ in range(n + 1)]  # 인접 리스트로 그래프 표현
visited = [0] * (n + 1)  # 방문 여부 기록
result = []  # 촌수 저장

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

def dfs(v, num):
    visited[v] = 1  # 현재 정점 방문 처리
    num += 1  # 촌수 증가

    if v == b:  # 목표 정점에 도달한 경우
        result.append(num)

    for i in graph[v]:  # 연결된 정점 탐색
        if visited[i] == 0:  # 방문하지 않은 정점에 대해 재귀 호출
            dfs(i, num)

dfs(a, 0) # DFS 탐색 수행

if len(result) != 0:
    print(result[0] - 1)  # 촌수는 탐색 깊이 - 1
else:
    print('-1')  # 연결되지 않은 경우