[BOJ] 2644. 촌수 계산

Python3

문제

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

키워드

• 그래프 탐색
• 너비 우선 탐색
• 깊이 우선 탐색

문제 풀이

문제 요구사항

여러 사람들에 대한 부모 자식들 간의 관계가 주어졌을 때, 주어진 두 사람의 촌수를 계산하는 프로그램을 작성하시오.

(기본적으로 부모와 자식 사이를 1촌으로 정의하고 이로부터 사람들 간의 촌수를 계산한다.)
ex) 나와 아버지, 아버지와 할아버지는 각각 1촌으로 나와 할아버지는 2촌이 되고, 아버지 형제들과 할아버지는 1촌, 나와 아버지 형제들과는 3촌이 된다.

변수 및 함수 설명

• n : 전체 사람의 수
• a, b: 촌수를 계산해야 하는 서로 다른 두 사람의 번호
• m: 부모 자식들 간의 관계의 개수
• x, y: 부모 자식간의 관계를 나타내는 두 번호 (이때 앞에 나오는 번호 x는 뒤에 나오는 정수 y의 부모 번호를 나타낸다.
  각 사람의 부모는 최대 한 명만 주어진다.)

• queue: bfs함수를 수행하기 위한 큐
• adjList: 촌수가 저장되어 있는 리스트
• visited: 방문 처리 리스트
• curNum: 현재 촌수를 계산하는 번호

풀이

(입력 및 선언)

• 전체 사람의 수를 입력 받는다.
• 촌수를 계산해야 하는 서로 다른 두 사람의 번호를 입력 받는다.
• 부모 자식들 간의 관계 개수를 입력받는다.
• 해당 m만큼 반복문을 수행한다.
• 부모 자식 간의 관계를 입력받고 adjList에 저장한다.

(bfs 함수)

• 큐에 촌수를 계산해야 하는 번호(a)를 넣고, bfs함수를 호출한다.
• 큐에 원소가 있을 때까지 반복한다.
• 첫 번째 큐에 있는 원소를 curNum 변수에 저장한다.
• curNum과 관련 있는 숫자를 adjList에서 탐색한다.
• 만약 방문하지 않은 곳이면, 방문 처리를 해주고 큐에 해당 원소를 넣는다.

(최종 출력)

• 만약 촌수를 계산하는 번호(b)의 방문 처리 리스트가 0보다 크면, 촌수를 계산할 수 있으므로 해당 원소를 출력한다.
• 그렇지 않으면 계산할 수 없다는 것이므로 -1을 출력한다.

최종 코드

from collections import deque

n = int(input())

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

queue = deque([])
adjList = [[] for _ in range(n+1)]
visited = [0 for _ in range(n+1)]

def bfs():
    while queue:
        curNum = queue.popleft()
        for element in adjList[curNum]:
            if visited[element] == 0:
                visited[element] = visited[curNum] + 1
                queue.append(element)

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

    adjList[x].append(y)
    adjList[y].append(x)

queue.append(a)
bfs()

if visited[b] > 0:
    print(visited[b])
else:
    print(-1)