[백준 2024/02/11] 1260번 DFS와 BFS

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

1260번: DFS와 BFS

 

1. 접근 방법

DFS와 BFS 중 구현하기 더 어려웠던 것을 고르자면, DFS라고 할 수 있다. 

 

1) BFS의 경우, 1번 노드(v라고 가정)가 가리키는 모든 노드를 돌고, 먼저 간 노드를 다음으로 방문하면 된다.

 

아래 예제로 시각화하여 다시 나타내 보자면 ...

일단, 노드들의 방문 경로를 list로 나타내 주었다.

 

추후 설명을 위해 4-5, 5-4를 넣어두었다.

 

1번 노드가 갈 수 있는 경로: 1-2, 1-3, 1-4

2번 노드가 갈 수 있는 경로: 2-1, 2-4

3번 노드가 갈 수 있는 경로: 3-1, 3-4

4번 노드가 갈 수 있는 경로: 4-1, 4-2, 4-3, 4-5

5번 노드가 갈 수 있는 경로: 5-4

[각 노드별 이동경로를 오름차순으로 정렬해주는 것을 잊지 말자] 

 

 

이런식으로 나타내주었다.

v가 1이므로, result = [1]

1-2, result = [1, 2]

1-3, result = [1, 2, 3]

1-4, result = [1, 2, 3, 4]

를 차례대로 이동해주었다. 방문할 때마다 result라는 list에 값을 넣어주었다.

 

이번 예제는 이로 끝이 나지만, 4-5, 5-4가 추가되어 있다고 생각해보자.

그렇다면 1 -> 2-> 3 -> 4 로 다시 순회하며, 남은 노드들을 추가시켜 주어야 한다.

1 -> 2 -> 3 -> 4 로 순회하는 이유는, BFS는 먼저 순회한 노드부터, 우선순위로 순회하기 때문이다.

이를 통해 4를 순회할 때, 4-5 경로를 이용해서 5번 노드도 방문을 완료하게 된다.

 

2) 이제 DFS에 대해서 알아보도록 하자.

처음에 DFS에 대해서 잘못 이해하고 코드를 작성했어서, 이 부분에서 많은 어려움을 겪었었다.

부디, 구글에 DFS 를 검색해서 사진을 보고 확실히 이해하길 바란다..ㅜ

 

출처: https://www.freelancinggig.com/blog/2019/02/06/what-is-the-difference-between-bfs-and-dfs-algorithms/

 

오른쪽이 DFS이다. DFS 구현의 주된 쟁점은, 지나왔던 노드를 다시 돌아가서, 아직 search하지 못한 노드를 다시 찾는다는 점이다.

 

아래 예제로 DFS를 시각화해서 생각해보자.

 

15 14 1
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
5 11
6 12
6 13
7 14
7 15

 

DFS: 1 2 4 8 9 5 10 11 3 6 12 13 7 14 15

 

그래프 구조: 

1
2 3
4 5 6 7
89 1011 1213 1415

 

list에 저장되는 값은 아래와 같다.

[[], [2, 3], [1, 4, 5], [1, 6, 7], [2, 8, 9], [2, 10, 11], [3, 12, 13], [3, 14, 15], [4], [4], [5], [5], [6], [6], [7], [7]]

즉, 

1번 노드: 1-2, 1-3

2번 노드: 2-1. 2-4, 2-5

3번 노드: 3-1, ...

 

여기서 문제는 8번까지 찾아내고 난 후, 4번으로 올라가서 9번을 search 해야한다는 점이다.

이는 back 이라는 List를 만들어서 방문 여부를 확인하고자 하였다.

        if changed == False:
            back.append(v)
            for i in range(-1, -len(result)-1, -1):
                if result[i] not in back:
                    v = result[i]
                    break

만약, 특정 노드에서 어떤 노드로도 방문을 하지 못했다면, back이라는 list에 값을 넣어주었다. -> back.append(v)

이후, result list 즉, 방문했던 list에서 뒤에서 부터 접근한다. 이때, back list에 들어가 있는 노드라면, 이미 어떤 노드로도 방문을 하지 못하는 상태임을 알기 때문에, 해당 경우는 넘어가 주었다.

 

result list에서 뒤에서 부터 접근하는 이유는, 가장 최근에 방문한 노드에서 부터 다시 밑으로 내려가야하기 때문이다.

result = [1, 2, 4, 8] 인 상태에서, 8번 노드는 이미 back에 들어가 있는 노드이기 때문에 건너 뛰어주고, 그 다음 노드인 4를 다음 search 대상으로 여겨, v 값으로 설정한다. 

 

이를 통해 다시 while 문을 돌게 되면, 4 번 노드의 경우 8 번을 이미 방문 했기 때문에 9번을 이제 방문하게 될 것이다.

9 번 노드는 이제 다시 방문할 노드가 없기 때문에, back list에 들어가게 되고,

 

result = [1, 2, 4, 8, 9] 에서 다음 대상을 찾게 된다.

9, 8 번은 back list에 들어가 있기 때문에 대상이 되지 못하고, 4가 다음 대상이 되게 된다.

 

하지만 4번을 돌게 되면 이미 8, 9 가 result list에 들어가 있기 때문에, 즉 이미 방문 했기 때문에 4번도 이제는 갈 노드가 없어졌다.

이렇게 되면 4번도 back list에 들어가게 되고,

 

result = [1, 2, 4, 8, 9] 에서 다음 대상을 찾게된다.

4, 8, 9 는 back list에 들어가 있으므로, 다음 대상은 2가 되게 되고 ... 이를 반복한다.

---

while len(result) != length_nodes:

while 문은 length_nodes 라는 변수를 기준으로 설정해주었다.

처음에 n으로 기준을 설정해주었지만, 다음의 경우 너무 비효율적이기 때문이다.

노드는 1000개이지만, 간선 수는 1개 이다.

따라서, 직접 간선에 이용되는 노드의 개수를 세주었다. 

위의 예제의 경우 999, 1000  -> 2개 이기 때문에 length_nodes는 2가 되었다.

 

++ v = 1 (시작 노드가 1) 이지만, 간선에 1이 사용되지 않는 경우를 주의하길 바란다. 이 때에는 

1

1

이 답으로 출력 되어야 한다.

2. 코드

def DFS(length_nodes, list_n, v):
    result = []
    result.append(v)
    back = []
    while len(result) != length_nodes:
        changed = False
        for k in list_n[v]:
            if k not in result:
                v = k
                result.append(v)
                changed = True
                break
        if changed == False:
            back.append(v)
            for i in range(-1, -len(result)-1, -1):
                if result[i] not in back:
                    v = result[i]
                    break

    return ' '.join(map(str, result))

def BFS(length_nodes, list_n, v):
    result = []
    result.append(v)
    i = 0

    while len(result) != length_nodes:
        for n in list_n[result[i]]:
            if n not in result:
                result.append(n)
        i += 1

    return ' '.join(map(str, result))

n, m, v = map(int, input().split())
list_node = [[] for _ in range(n+1)]

nodes = []

for i in range(m):
    start, end = map(int, input().split())
    list_node[start].append(end)
    list_node[end].append(start)
    if start not in nodes:
        nodes.append(start)
    if end not in nodes:
        nodes.append(end)

for sublist in list_node:
    sublist.sort()

#print(list_node)

if v not in nodes:
    print(v)
    print(v)
else:
    print(DFS(len(nodes), list_node, v))
    print(BFS(len(nodes), list_node, v))