백준 2644번(촌수계산) 파이썬

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

2644번: 촌수계산

하아... 다시 또 벽을 느낀 문제였다.

이젠 거의 다 안다고 생각했는데 그러지 못했다.

문제의 접근 방식이 틀렸었다.

결국 다른사람의 코드를 참고했다.

아직 갈길에 먼거같다...

 

import sys
sys.setrecursionlimit(10**9) 

input = sys.stdin.readline

N = int(input())
a,b = map(int,input().split())
M = int(input())

graph=[[0]*(N+1) for _ in range(N+1)]
visited = [0]*(N+1)

for _ in range(M):
    x,y = map(int,input().split())
    graph[x].append(y) # 서로 이어져 있는 노드이니
    graph[y].append(x) # 서로 추가해준다.

def dfs(a):
    for i in graph[a]: # a번째 그래프에 들어있는 노드들의 차례대로 탐색해간다
        if(visited[i] == 0): # 미방문했다면 
            visited[i]=visited[a]+1 # a노드에 +1을 해주며 이어진 간선의 갯수를 세준다
            dfs(i) # 그리고 재귀
    

dfs(a)
print(visited)
if visited[b] != 0: # 방문하지 않은 노드는 아예 연결이 안되어있는 노드이기 때문에
    print(visited[b]) 
else:
    print(-1) # -1을 출력해준다.

개인적으로 bfs보다 dfs가 더 어렵게 느껴진다. 

앞으로 dfs 문제를 좀 더 중점적으로 풀어봐야 할 거 같다.