[백준/Python] 2644번(그래프이론, 그래프탐색, DFS,BFS)_촌수계산

📌문제 유형

그래프이론, 그래프탐색, DFS, BFS (실버2)

 

📌문제

2644번: 촌수계산

 

📌나의 문제풀이

- 실패

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

def find_parent(parent, x):
    if parent[x] != x:
        return find_parent(parent, parent[x])
    return parent[x]
    
def union_parent(parent, a,b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)

    if a < b:
        parent[b] = a
    else:
        parent[a] = b

# 여기만 수정해보기 
def cnt_degree(graph,a,b,ans):
    if a in graph[b]:
        return ans

    for num in graph[b]:
        if b not in graph[num]:
            ans += 1
            cnt_degree(graph,a,graph[num])
            

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

print(graph)

if parent[a] != parent[b]:
    print(-1)
else:
    print(cnt_degree(graph,a,b,0))  # 자식에서 타고 올라가기

 

📌 다른사람의 문제풀이

[백준 python] 2644번 촌수계산 DFS - 파이썬

[파이썬] 2644번 '촌수계산' 문제 풀이

# 입력값 받는 부분
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
def dfs(v):
    visited[v] = True
    for i in graph[v]:
        if not visited[i]:
            res[i] = res[v] + 1
            dfs(i)

n=int(input())
A,B=map(int,input().split())
m=int(input())

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


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

dfs(A)

if res[B]>0:
    print(res[B])
else:
    print(-1)

# BFS
from collections import deque

def bfs(s):
    queue=deque([s])
    visited[s]=True

    while queue:
        v=queue.popleft()

        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                res[i]=res[v]+1
                visited[i]=True

n=int(input())
A,B=map(int,input().split())
m=int(input())

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


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

bfs(A)
if res[B]>0:
    print(res[B])
else:
    print(-1)

 

📌 리뷰

- DFS 확인할 때, 겹치지 않도록 노드 방문 여부도 체크하기