[백준/Python] 2644번 - 촌수계산

문제

2644번 - 촌수계산

문제 해결 과정

• 기본 DFS문제
• 탐색 시작 노드는 촌수를 계산해야 하는 서로 다른 두 사람의 번호 중 하나
• 탐색 시작 노드가 아닌 또 다른 하나의 번호를 방문했을 때 result에 값 추가
• dfs를 끝까지 돈다.

시행 착오

• bfs로 풀었다가..dfs로 다시 풀었음
• 복잡하게 생각해서 어려웠던 것 같다.
  • 두 개의 번호가 각각 최상단 노드까지 가는 거리를 더해서 촌수를 구할려고 했는데,
  • 최상단 노드가 다를 때의 구현이 어려웠다.
• dfs를 이용해서 최하단 노드에서 최상단 노드로 가보고,,
• 조건문을 만들고 리스트를 이용해서 cnt값을 추가하고 재귀는 계속 돈다.
  • 반복문에서의 break만 생각이 났다

틀린 코드

• cnt를 파라미터로 주지 않고, global로 사용했을 때
  • cnt값은 1,2,3,4,5,6
• cnt를 파라미터로 줄 경우
  • cnt값은 1,2,3,4,3,3

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

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

for _ in range(m):
  x, y = map(int,sys.stdin.readline().split())
  graph[x].append(y)
  graph[y].append(x)
  
result = []
cnt = 0

def dfs(graph,v,visited):
  global cnt
  cnt += 1
  visited[v] = True
  
  if v == b:
    result.append(cnt)
    
  for i in graph[v]:
    if not visited[i]:
      dfs(graph,i,visited)

dfs(graph, a, visited)

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

풀이

import sys
## 입력 받기
n = int(sys.stdin.readline())
a,b = map(int,sys.stdin.readline().split())
m = int(sys.stdin.readline())

visited = [False] * (n+1)
# 2차원 배열
graph = [[] for _ in range(n+1)]
result = []

# 배열에 노드의 값들 넣기
for _ in range(m):
  x, y = map(int,sys.stdin.readline().split())
  graph[x].append(y)
  graph[y].append(x)

# DFS 구현
def dfs(v,cnt):
  cnt += 1
  visited[v] = True
  # 찾아야 하는 사람의 번호를 방문했을 때
  if v == b:
    result.append(cnt)
  for i in graph[v]:
    if not visited[i]:
      dfs(i,cnt)

dfs(a,0)

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