[BOJ] #2644_촌수계산(Python3, 파이썬)

본 게시글은 백준 저지 알고리즘 문제를 '파이썬, Python3' 언어로 풀이한 내용을 주관적으로 정리하였으며, 내용과 관련된 코드리뷰 및 피드백 환영합니다.

티어

Silver II

문제 출처

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

---

풀이

# DFS

import sys
input = sys.stdin.readline

n = int(input()) # 전체
a, b = map(int, input().split()) # 촌수계산해야하는 번호 둘
m = int(input())
graph = [[] for _ in range(n+1)]
visited = [False] * (n+1)
result = []

# 연결되어있는 노드들을 graph에 저장
for _ in range(m):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)

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문제이다. 먼저 값들을 모두 입력받아둔 다음, 노드들을 저장하고, 노드들을 방문처리하며 v 값이 B와 같을 때 result에 저장해주었다