[백준 파이썬] 2644 촌수계산

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

2644번: 촌수계산

 

문제

사촌간의 관계가 주어지고 촌수를 계산하는 문제이다.

---

아이디어

입력값으로 각각의 인원에 대한 정보값이 주어진다. 

해당 정보를 바탕으로 그래프를 만든 뒤 깊이 우선탐색으로 해결하면 되겠다고 생각했다.

---

풀이

먼저 그래프에 관한 정보를 입력받는다

graph = [[] for _ in range(n + 1)]
visited = [-1] * (n + 1)

result = []

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

사촌의 경우 양방향 그래프이므로 입력받는 관계에 대해 양방향으로 입력해준다.

 

def DFS(v, num):
  num += 1
  visited[v] = 1

  if v == end:
    result.append(num)
  
  for i in graph[v]:
    if visited[i] == -1:
      DFS(i, num)

DFS의 구현은 다음과 같다.

촌수를 계산할 num값과 촌수를 확인할 사람 v를 입력값으로 받는다.

만약 v값이 도달값(end)와 같다면 result에 입력한다.

v값과 연결된 사람에 대해 방문하지 않았다면 DFS를 사용해 탐색한다.

 

if len(result) == 0:
  print(-1)
else:
  print(result[0]-1)

출력은 위와 같다.

만약 result의 길이가 0이라면 방문하지 못했다는 의미이므로 사촌이 아니라고 판단하여 -1을 출력한다.

아닌 경우에는 result값을 출력한다.

 

 

---

코드

n = int(input())
start, end = map(int, input().split())
m = int(input())
graph = [[] for _ in range(n + 1)]
visited = [-1] * (n + 1)

result = []

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

def DFS(v, num):
  num += 1
  visited[v] = 1

  if v == end:
    result.append(num)
  
  for i in graph[v]:
    if visited[i] == -1:
      DFS(i, num)

DFS(start, 0)
if len(result) == 0:
  print(-1)
else:
  print(result[0]-1)