[파이썬] BOJ_2644(촌수계산)

 

 

문제

 

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

2644번: 촌수계산

---

 

해설

 

입력값을 받고 그래프를 생성하는 부분을 지나면 dfs 혹은 bfs로 문제를 풀어야 한다.

dfs로 풀 때는 촌수를 cnt에 저장했다. 함수 한 번 씩 돌 때 마다 촌수가 1씩 올라간다.

 

 

반응형

 

bfs로 풀 때는 deque를 이용하면 된다. 따로 촌수를 받을 필요는 없고

visited 변수에 현재 visited 값에 1촌을 더해서 저장해주면 된다.

처음 a를 1로 시작하는데 a 자신은 0촌 이기 때문에 마지막에 출력할 때 1을 빼주면

원하는 촌수를 구할 수 있다.

a의 visited값에 1을 넣어주고 시작하지 않으면 for문을 돌 때 a를 다시 만나면 visited[a]가 0이라 

잘못된 촌수가 들어갈 수 있기 때문에 마지막에 1을 빼주게 되더라도 visited[a]에 1을 넣고 시작해야 한다.

---

코드

 

-파이썬

#백준 2644(촌수계산)
from collections import deque

n = int(input())  #전체 사람 수
a, b = map(int, input().split())  #촌수 계산할 사람 둘
m = int(input())  #부모-자식 관계 개수
graph = [[] for _ in range(n+1)]  #그래프 초기화
visited = [0] * (n+1)  #방문 여부

for i in range(m):  #그래프 생성
    x, y = map(int, input().split())  #부모, 자식
    graph[x] += [y]
    graph[y] += [x]

#DFS로 푸는 방법
def dfs(v, cnt):
    if v == b:  #찾아야 할 사람일 때
        print(cnt)
        exit()
    visited[v] = 1
    cnt += 1  #촌수
    for next in graph[v]:
        if visited[next] == 0:
            dfs(next, cnt)

dfs(a, 0)
print(-1)

# ------------------------------------------------

#BFS로 푸는 방법
def bfs(v):
    Q = deque([v])
    visited[v] = 1
    while Q:
        current = Q.popleft() 
        if current == b:  #찾아야 할 사람
            print(visited[current] - 1)
            break
        for next in graph[current]:
            if visited[next] == 0:
                visited[next] = visited[current] + 1
                Q.append(next)

bfs(a)
if visited[b] == 0:
    print(-1)