[2644]촌수 계산

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

2644번: 촌수계산

 

처음엔 DFS로 접근을 하려고 했으나..문제가 있었다.

n = int(input())
a, b = map(int, input().split())
m = int(input())

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

visited = [False]*(n+1)

count = 0
def dfs(v):
    global count
    visited[v] = True
    if v == b:
        return count  

    for i in graph[v]:
        if not visited[i]:
            visited[i] = True
            count += 1
            dfs(i)

# main
dfs(a)

if not visited[b]:
    print(-1)
else:
    print(count%2 + count//2)

count를 전역변수로 두어 계산을 하려고 했으나.. count가 경로에 상관없이 지나가는 곳마다 더해진다.

몫과 나머지를 더해 출력하는 방식으로 생각을 했지만 틀린 접근법이었다.

 

n = int(input())
a, b = map(int, input().split())
m = int(input())

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

visited = [False]*(n+1)

def dfs(v, count):
    global flag
    visited[v] = True
    if v == b: 
        flag = True
        print(count)

    for i in graph[v]:
        if not visited[i]:
            dfs(i, count+1)
# main
flag = False
dfs(a, 0)

if not flag:
    print(-1)

flag를 세워두고 푸는 풀이도 있었지만, return이 아닌 print로 처리하여 좀 찝찝한 감이 있다.

# 입력값 받는 부분
N = int(input())
A, B = map(int, input().split())
M = int(input())
graph = [[] for _ in range(N+1)]
visited = [False] * (N+1)
result = []
####

# 어떤 노드들이 연결되어 있는지 graph라는 2차원 배열에 저장
for _ in range(M):
  x, y = map(int, input().split())  
  graph[x].append(y)
  graph[y].append(x)

# dfs
def dfs(v, num):
  num += 1
  visited[v] = True

  if v == B:
    result.append(num)

  for i in graph[v]:
    if not visited[i]:
      dfs(i, num)

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

 

dfs 함수 내에서 num(count) 변수가 중첩되어 출력이 되지 않게 처리를 하였다.

이렇게 하게되면 같은 촌수 내 count 중첩 없이 촌수 계산이 가능하다.