[백준] 2644 .촌수계산

처음에 이런식으로 트리로 생각해서 그림을 그려서 했는데, 자식노드만 트리에 넣어주니까 어떻게 해야할지 몰랐다.

 

 

그래서 이런식으로 그림을 바꿔 그렸다.

 

연결되어있는 간선의 수를 찾으면 되므로 tree라는 리스트에 해당 인덱스의 노드가 만나는 노드들을 넣어주었다.

[[], [2, 3], [1, 7, 8, 9], [1], [5, 6], [4], [4], [2], [2], [2]]

그래서 dfs를 이용해서 인접한노드들을 방문했다고 체크하고 dfs함수에 그 노드를 넣었다. 함수를 넘길 때 동시에 cnt를 인자로 넣어서 얼마나 이동을 했는지 세주었고, 찾고자 하는 값 b와 같은 노드를 만난다면 result에 cnt값을 넣어주고 return을 시켰다.

서로 다른 트리에 노드가 있어서 연결되어있지 않을 때는 -1을 출력해줘야 하기 때문에 result의 초기값은 -1로 두었다.

---

def DFS(num,cnt):
    global result,b
    if num == b:
        result = cnt
        return
    for i in range(len(tree[num])):
        if visited[tree[num][i]] == False:
            visited[tree[num][i]] = True
            DFS(tree[num][i], cnt+1)

n = int(input())
a, b = map(int, input().split()) # 촌수를 계산해야 하는 서로 다른 두 사람의 번호
m = int(input()) 
tree = [[] for _ in range(n+1)]
visited = [False]*(n+1)

for i in range(m):
    x, y = map(int, input().split())
    tree[x].append(y)
    tree[y].append(x)
# print(tree)
# print(visited)

result = -1

DFS(a,0)
print(result)