DFS 재활훈련 - return이 있는 DFS 작성하기 연습 + 트리의 경로 유일성 배우기

1. 문제1

 

13023번: ABCDE (acmicpc.net)

13023번: ABCDE

 

 

2. 풀이

 

A는 B의 친구이다

 

B는 C의 친구이다

 

C는 D의 친구이다

 

D는 E의 친구이다

 

이 말은 무슨말일까?

 

A에서 시작해서 B로 가고, B에서 C로 가고 C에서 D로 가고 D에서 E로 갈 수 있는 경우가 존재하는지 아닌지를 판단하라는 말

 

주어진 그래프에서 DFS 탐색으로 깊이 4까지 갈 수 있다면 1을 return하면 될 것

 

깊이가 4이면 1을 return하고..

 

깊이가 4가 아니면.. 탐색을 수행

 

현재 방문하는 점 x에 대한 방문처리 visited[x] = 1

 

x와 연결된 점 graph[x]에서 순회해서...

 

방문하지 않는 점.. visited[f] == 0인 f에 대해 깊이 1을 증가시키고 다음 dfs를 수행

 

answer = dfs(f,s+1,visited)

 

이 answer이 1이면 탐색을 진행하지 않아도 되니 계속 1을 return해준다

 

재귀 탐색에서 return하면서 다음 재귀 경로를 탐색하기 위해 visited[f] = 0으로 바꿔주는 것도 잊지말고

 

from sys import stdin

def dfs(x,s,visited):
    
    if s == 4:
        
        return 1
    
    else:
        
        visited[x] = 1

        for f in graph[x]:
            
            if visited[f] == 0:
                
                answer = dfs(f,s+1,visited)

                if answer == 1:
                    
                    return 1
                
                visited[f] = 0

        return 0

n,m = map(int,stdin.readline().split())

graph = [[] for _ in range(n)]

for _ in range(m):
    
    a,b = map(int,stdin.readline().split())

    graph[a].append(b)
    graph[b].append(a)

for i in range(n):

    visited = [0]*n

    answer = dfs(i,0,visited)

    if answer == 1:
        
        break

print(answer)

 

그리고 모든 가능한 경우를 조사해봐야하니까 시작점을 0번부터 n-1번까지 순회해야할 것이고..

 

 

2. 문제2

 

1240번: 노드사이의 거리 (acmicpc.net)

1240번: 노드사이의 거리

 

3. 풀이

 

"트리에서 두 노드 사이 경로는 유일하다"

 

트리는 루트 노드(부모 노드가 0개)를 제외한 모든 노드가 정확히 1개의 부모 노드만을 가진다.

 

그리고 트리는 사이클이나 루프가 없다

 

그러므로 어떤 두 정점 사이 경로는 유일하다

 

이게 무슨 의미나면.. 이 문제에서 최단 거리 알고리즘을 사용할 필요가 없다는 뜻

 

단순히 해당 두 노드 사이를 탐색해서 거리를 구하기만 한다면 그 거리가 두 노드 사이 거리라는 뜻이다

 

근데.. 생각없이 그냥 풀었는데

 

아무튼 이 문제도 return을 주는 DFS로 작성해보자

 

x와 y사이 거리를 구하고자 할때, x == y라면 거리 s를 return해주고

 

x와 y가 다르다면 탐색을 수행

 

현재 방문 지점 x를 방문처리하고..

 

x에서 연결된 지점중에서 방문하지 않은 점 i를 찾아서 i로 dfs를 들어간다

 

이 dfs 결과가 -1이 아니라면.. y에 도달했다는 뜻이므로 더 이상 탐색하지 말고 계속 answer값을 return해준다

 

그리고 answer = -1인 경우 다음 재귀 경로 탐색을 위해 visited[x] = 0으로 바꿔주고 새로 탐색해야한다는 점

 

from sys import stdin

def dfs(x,y,s,visited):
    
    if x == y:
        
        return s
    
    else:
    
        visited[x] = 1
            
        for i in range(1,n+1):

            if graph[x][i] != 0 and visited[i] == 0:
                
                answer = dfs(i,y,s+graph[x][i],visited)

                if answer != -1:
                    
                    return answer

                visited[i] = 0
        
        return -1
n,m = map(int,stdin.readline().split())

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

for _ in range(n-1):
    
    a,b,c = map(int,stdin.readline().split())

    graph[a][b] = c
    graph[b][a] = c

for _ in range(m):
    
    p,q = map(int,stdin.readline().split())

    visited = [0]*(n+1)

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

 

 

이 문제는 graph를 인접행렬로 받아서 작성해봄..

 

왜냐하면 두 정점 사이 거리가 1이 아니라서

 

그랬더니 x에서 연결된 지점을 찾을려면 1부터 n까지 항상 순회해야하고.. 그 중에서 graph[x][i]가 0이 아닌 지점이 연결된 지점

 

 

 

 

 

[Graph] Graph 이론 (tistory.com)

[Graph] Graph 이론