03/17(Wed) DFS와 BFS (1)

✍🏼

DFS 와 BFS 그리고 재귀함수.

개념과 이를 구현한 코드를 제대로 이해 하지 않고 넘어 갔더니, 산을 만났다.

난이도가 중인 문제 3개가 남았는데, 전부 풀 수 없었다. DFS, BFS, 재귀를 이용해서 코드를 만들어야 하는 문제를 어떻게 풀 수 있겠는가.

 

이제 어쩔 수 없으니 DFS와 BFS를 알아보자.

---

1. DFS (Depth First Search, 깊이 우선 탐색)

 

깊이 우선 탐색의 예시

깊이 우선 탐색은 맹목적 탐색의 방법의 하나로 탐색트리의 최근에 첨가된 노트를 선택하고, 이 노드에 적용 가능한 동작자 중 하나를 적용하여 트리에 다음 수준의 한 개의 자식노드를 첨가하며, 첨가된 자식 노드가 목표노드일 때까지 앞의 자식 노드의 첨가 과정을 반복해 가는 방식이다.

-위키백과

 

 

아직 초보라 개념만 읽어선 무슨 말인지 모르겠고, 위의 그림을 보는 편이 더 낫다.

1번부터 10번까지 저런 순서대로 탐색을 한다. 더 이상 연결된 번호가 없을 때까지 쭉 파고 내려간다.

구글링하다가 어떤 블로그에서 DFS는 이어달리기 바톤터치와 비슷하다는 글을 보고 난 뒤로 DFS에 대한 이해가 완벽히 됐다.

하지만 이를 구현한 코드를 짜는 게 어려워서 개념 이해만 하고 넘어갔었는데, 더 이상 피할 수 없어서 오늘은 DFS, BFS를 코드로 구현해보는 걸 목표로 삼았다.

 

 

---

백준 1260번 문제를 보면서 DFS에 대해 알아보자.

 

예제 입력 2를 들고 왔다.

 

5 5 3

5 4

5 2

1 2

3 4

3 1

 

첫째 줄에 나와있는 5 5 3은 순서대로 'n = 정점의 개수, m = 간선의 개수, v = 정점의 번호' 라고 한다.

이건 나중에 코드 칠 때 생각해보기로 하고, 둘째 줄부터 마지막 줄 까지 나와있는 숫자들은 간선이 연결하는 두 정점의 번호라는데,

이게 무슨 말인지 이해도 못했었다.

 

말로 풀어서 설명하자면,

 

숫자 5는 4와 연결돼있고,

숫자 5는 2와 연결,

숫자 1은 2와 연결,

숫자 3은 4와 연결,

숫자 3은 1과 연결 돼있다는 뜻이다.

 

의식의 흐름대로 그렸더니 이상한 모양이 돼서 고쳤다.

 

# 작은 숫자가 왼쪽에 오도록 수정한 이유는 얘네를 for문 돌려서 리스트에 넣을 거라 결국엔 오름차순으로 정리 되게 된다.

 

1) 딕셔너리로 정리하자

 

1: [2, 3]

2: [1, 5]

3: [1, 4]

4: [3, 5]

5: [2, 4]

 

숫자들이 서로 어떻게 연결 돼있는지 딕셔너리로 정리해놓고, 곧 만들 리스트와 같이 놓고 보면서 코드를 짜야 한다.

tool = [[0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0]]

이렇게 6 X 6으로 된 list를 만든다. tool의 index == 숫자랑 맞추기 위해 5 X 5가 아니라 6 X 6으로 만들었다.

이제 딕셔너리로 정리해 놓은 걸 보면서 tool에 체크를 해보자.

 

1은 2와 3이랑 만나니까 1열 [2]와 [3] 자리에 1로 바꾼다.

== 1이 2와 3이랑 만난다는 건 2도 1과 만나고, 3도 1과 만난 다는 뜻이니까, 얘네도 1로 바꾼다.

 

2는 1과 5를 만나니까 2열 [1]와 [5] 자리에 1로 바꾼다. ( 반대의 경우도 마찬가지로 체크)

이렇게 마지막 숫자 5까지 서로 연결되는 숫자들을 1로 바꿔준다.

 

tool = [[0, 0, 0, 0, 0, 0],
        [0, 0, 1, 1, 0, 0],
        [0, 1, 0, 0, 0, 1],
        [0, 1, 0, 0, 1, 0],
        [0, 0, 0, 1, 0, 1],
        [0, 0, 1, 0, 1, 0]]

1로 다 바꿔주고 나면 이렇게 나온다.

 

DFS든 BFS든 여기까지 이해했으면 반은 온 거라고 생각한다. DFS와 BFS 개념 이해는 하겠는데, 이걸 코드로 어떻게 짜야할지 모르겠어서 별 방법을 다 써가면서 코드를 짰었는데, 전부 하다가 막혔다.

 

각 숫자들이 서로 어떻게 연결 돼있는지는 알겠는데, 그래서 이걸 어디다가 저장을 해놓아야 하며, 어떻게 저장을 해놓아야 하는지 몰랐다.

 

오늘 다른 팀원분이 DFS, BFS를 저렇게 리스트에 넣어가면서 설명을 해주셨는데, 저 리스트 보자마자 "아, 저거다. 저렇게 하면 할 수 있겠다" 라는 생각이 들었다.

 

# 입력 받아야 할 값들
n, m, start_node = map(int, input().split())

# 연결 여부를 체크해 놓을 리스트 준비(0부터 넣어서 좌표처럼 활용)
tool = [[0 for _ in range(n+1)] for _ in range(n+1)]

# 번호를 받고, 딕셔너리로 만든 후 -> 연결된 번호들을 좌표로 넣어서 1로 체크 해놓자.
for _ in range(m):
    x, y = map(int, input().split())
    tool[x][y] = tool[y][x] = 1

 여기까지의 코드.

 

DFS 다 정리하고 자러 가려고 했는데, 깃헙 강의랑 칸 수학문제도 풀러 가야 한다.

나머지는 내일 정리해야지.

 

 

 

# update

 

2021.03.18 - [HangHae99/TIL-hanghae99] - 03/18(Thu) DFS와 BFS (2)

03/18(Thu) DFS와 BFS (2)