[BOJ] 2644번 촌수계산 / 사용언어 : 파이썬(python)

※ 문제링크

2644번: 촌수계산

해당문제는 그래프 탐색과 관련된 문제로 BFS, DFS로 해결할 수 있는 문제였다. DFS는 재귀한계를 따로 수정해주지 않으면, recursion 에러가 발생하기에 추가적인 설정을 할 필요가 없는 BFS로 문제를 해결하였다. BFS를 작성하기 위해 파이썬의 deque를 사용하여 문제를 해결하였다. 자세한 문제풀이방법과 코드는 아래와 같다.

1. 입력받은 값들을 2차원 리스트를 활용하여 그래프형태로 구현해준다.(문제에서 각각의 간선은 양방향임을 기억하자)

2. 촌수를 계산할 BFS함수를 작성한 후 결과값을 출력해준다.(구체적인 설명은 코드블록에서 확인해주세요).

3. 결과값이 inf면 -1을 아니면 해당 값을 출력한다. + 시간 및 메모리 절감을 위해 sys를 활용하였다.

 

# 구현에 필요한 패키지 로드
from collections import deque
import sys

# 입력값 저장 및 그래프 구현
# input = sys.stdin.readline
n = int(input()) 
p1, p2 = map(int, input().split())
m = int(input())
line = [[] for _ in range(n+1)]
for _ in range(m):
    s, e = map(int, input().split())
    line[s].append(e)
    line[e].append(s)

def bfs(p1, p2):
    queue = deque() # 그래프를 탐색하고 간선을 갱신할 queue생성
    visited = [False for _ in range(n+1)] # 방문여부를 확인할 리스트 생성
    relation = [float('inf') for _ in range(n+1)] # 관계차수를 갱신할 리스트 생성
    queue.append(p1) # 초기값 입력

    cnt = 0
    while queue:
        for _ in range(len(queue)):
            check = queue.popleft()
            if visited[check] == False: # 방문하지 않은 정점이 들어올 경우 명령문 실행
                relation[check] = cnt
                visited[check] = True
                queue.extend(line[check]) # 그래프에 리스트형태로 저장했으므로 extend로 값들을 queue에 저장
        # 한바퀴 다 돌때마다 촌수 증가명령
        cnt += 1
    
    if relation[p2] == float('inf'):
        print(-1)
    else:
        print(relation[p2])
    return

bfs(p1, p2)

 

P.S 더 나은 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다