📌 문제 탐색하기
👉 문제바로가기
n: 전체 사람의 수(1 ≤ n ≤ 100)
a, b: 촌수를 계산해야하는 서로 다른 두 사람의 번호
m: 부모 자식들간의 관계의 개수 m
x, y: 부모 자식간의 관계를 나타내는 두 번호(x는 y의 부모)
부모 자식들 간의 관계가 주어졌을 때, 이를 그래프로 구축하고 두 사람의 촌수(간선의 개수)를 구하는 문제입니다. 두 사람의 친척 관계가 전혀 없어 촌수를 계산할 수 없는 경우 -1을 출력해야합니다.
주어진 예제를 예시로 들어보겠습니다.
- 총 9명이 있습니다.
- 우리가 구해야하는 것은 7번과 3번의 촌수입니다.
- 부모 자식들 간의 관계의 개수는 7개입니다.
- 1번은 2번의 부모입니다.
- 1번은 3번의 부모입니다.
- 2번은 7번의 부모입니다.
- 2번은 8번의 부모입니다.
- 2번은 9번의 부모입니다.
- 4번은 5번의 부모입니다.
- 4번은 6번의 부모입니다.
위 정보를 그림으로 표현하면 아래와 같습니다.
주어진 부모 자식 관계를 통해 그래프를 구축하고, 3에서 시작하여 7까지 가는 간선의 수를 구하면 되는 문제입니다!
1️⃣ 입력 및 변수 정의
n = int(sys.stdin.readline())
a, b = map(int, sys.stdin.readline().split())
m = int(sys.stdin.readline())2️⃣ 노드정보 저장 및 그래프 기록
graph = [[] for _ in range(n+1)] #그래프 리스트 초기화
visited = [False] * (n+1) #방문 여부
for _ in range(m):
x, y = map(int, sys.stdin.readline().split()) #부모 자식 관계정보
graph[x].append(y)
graph[y].append(x)3️⃣ DFS함수 정의
우리가 구해야하는 것은 한 정점에서 다른 노드까지의 간선 개수입니다. 따라서 dfs의 매개변수인 v에는 인자를 a로하여 호출하면 됩니다.
def dfs(v):
global count
visited[v] = True
if v == b:
print(count)
exit()
for i in graph[v]:
if not visited[i]:
count += 1
dfs(i)
count -= 1 #재귀 호출이 끝나면 깊이 감소
dfs(s)
print(-1) dfs()에서 v == b인 경우 exit()를 만나 코드가 종료된다는 것은 우리가 찾고자하는 b를 만나면 자동으로 종료된다는 의미입니다. dfs()에서 코드가 종료되지 못하면.. 즉, for문을 모두 반복해도 원하는 값을 만나지 못하면 print(-1)이 실행됩니다.
📌 알고리즘 선택
한 점을 정점으로 선택하고 해당 점과 연결된 노드들을 모두 탐색하면서 원하는 값을 찾아야하기 때문에 DFS를 활용할 수 있겠네요.
시간복잡도
dfs함수가 한 번 호출되면, 현재 노드에서 가능한 모든 인접한 노드를 재귀적으로 탐색합니다. 모든 노드와 간선을 한 번씩 방문하므로 시간복잡도는 O(n+m)입니다. n의 최대값은 1000이고, 노드가 n개인 경우 부모-자식의 관계(간선의 수)는 n-1이므로 최대 999개가 됩니다. 따라서 최악의 경우 연산은 약 1999회가 수행되므로 이는 수행 시간 내에 충분히 연산이 가능합니다.
📌 코드 설계하기
- 전체 사람의 수(n), 촌수를 계산해야하는 서로 다른 두 사람의 번호, 부모 자식들간의 관계의 개수(m)을 Input받습니다.
- 부모 자식간의 관계를 나타내는 두 번호(x, y)를 입력받으면서 그래프를 구축합니다.
- DFS를 수행하면서 간선의 개수를 카운트합니다.
- 원하는 값을 가진 노드를 찾으면
count를 출력하고, DFS를 모두 수행했음에도 원하는 값을 찾지 못하면 -1을 출력합니다.
📌 정답 코드
import sys
count = 0
def dfs(v):
global count
visited[v] = True
if v == b:
print(count)
exit()
for i in graph[v]:
if not visited[i]:
count += 1
dfs(i)
count -= 1 #재귀 호출이 끝나면 깊이 감소
n = int(sys.stdin.readline())
a, b = map(int, sys.stdin.readline().split())
m = int(sys.stdin.readline())
graph = [[] for _ in range(n+1)] #그래프 리스트 초기화
visited = [False] * (n+1)
for _ in range(m):
x, y = map(int, sys.stdin.readline().split())
graph[x].append(y)
graph[y].append(x)
dfs(a)
print(-1)