[DFS] 족보

우리나라에서는 부모와 자식의 관계를 1촌이라고 한다.
따라서, 할아버지와 나는 2촌이 되고, 아버지가 아닌 할아버지의 아들은 3촌이 된다.
주어진 족보에 대해서, 두 사람의 촌수를 출력하시오.
단, 주어지는 족보에서는 부모 중에 한 사람만 표시되고, 친인척이 아닌 사람은 없다고 가정해도 된다.
또한, 촌수가 1,000,000 이상인 입력은 없다고 가정해도 된다.

Input
족보에 등장하는 사람은 모두 N명이고, 번호가 1번부터 N번까지 차례대로 부여되어 있다.
족보에 등장하는 부모와 자식 관계는 모두 M개이다.
첫째 줄에 양의 정수 N과 M이 주어진다.
둘째 줄에 촌수를 계산해야 하는 두 사람의 번호 P와 Q가 주어진다. (1 <= P, Q <= N)
셋째 줄부터 M개의 줄에 부모의 번호와 자식의 번호가 차례대로 주어진다.
9 8
7 3
1 2
1 3
2 7
2 8
2 9
3 4
3 5
5 6

9 8
8 6
1 2
1 3
2 7
2 8
2 9
3 4
3 5
5 6

Output
첫째 줄에 P와 Q의 촌수를 출력한다.
3

5

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

n, m = map(int, input().split()) # n명의 사람, m개의 관계
p, q = map(int, input().split()) # 촌수를 계산해야 하는 두 사람 -> start, end

# 부모의 번호와 자식의 번호 -> 양방향 그래프 생성
family = [[] for _ in range(n+1)] 
for _ in range(m):
    a, b = map(int, input().split())
    family[a].append(b)
    family[b].append(a)

#print(family)

# 깊이 우선 탐색
visited = [0]*(n+1)
def dfs(start, end, depth, family, visited):
    visited[start]=1
    if start==end:
        print(depth) # 깊이 출력
        return
    for i in family[start]:
        if visited[i]==0:
            dfs(i, end, depth+1, family, visited)
       

dfs(p, q, 0, family, visited)

 

 

 

 

 

 

---

start ~ end 까지 경로를 출력하고 싶으면 ...?

# 이동경로를 출력하고 싶으면 stack에 push, pop 해준다 
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

n, m = map(int, input().split()) # n명의 사람, m개의 관계
p, q = map(int, input().split()) # 촌수를 계산해야 하는 두 사람 start, end

# m개의 관계 -> 부모의 번호와 자식의 번호 -> 양방향 그래프 
family = [[] for _ in range(n+1)] 
for _ in range(m):
    a, b = map(int, input().split())
    family[a].append(b)
    family[b].append(a)

# print(family)

# 깊이 우선 탐색
visited = [0]*(n+1)
answer=[p] # 이동 경로 출력
def dfs(start, end, depth, family, visited):
    visited[start]=1 # 방문함
    if start==end:
        print("the depth of this graph is .. ", depth) # 깊이
        print("the route of this graph is ..", answer) # 이동 경로
        exit() # 목표에 도달했으면 강제종료
        #return
    for i in family[start]:
        if visited[i]==0:
            answer.append(i)
            dfs(i, end, depth+1, family, visited)
            answer.pop()
       

dfs(p, q, 0, family, visited)

 

 

---

P에서 될 수 있는 모든 촌수

# 모든 가족관계를 출력 P와 가능한 촌수
N, M = map(int, input().split())
P, Q = map(int, input().split())

G = [[] for _ in range(N+1)]
check = [0]*(N+1)

def DFS(cur, end, depth) :
    if cur==end :
        print(depth, end = ' ')
        return

    for node in G[cur] :
        if(check[node]==0) :
            check[node]=1
            DFS(node, end, depth+1)


for _ in range(M) :
    S, E = map(int, input().split())

    G[S].append(E)
    G[E].append(S)

check[P]=1

#DFS(P, Q, 0)

for i in range(1, N+1) :
    for j in range(N+1) :
        check[j] = 0

    print(P, " 와 ", i, "는 ", end=' ')
    DFS(P, i, 0)
    print('촌')