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

! 개인 기록용으로 TIL을 작성하며 한 번 더 정리해보는 것이라 코드가 완벽하지 않거나 정리가 미흡할 수 있습니다.

 

 

2021.03.18 - [HangHae99/TIL-hanghae99] - 03/17(Wed) DFS와 BFS (1)

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

 

1. DFS 코드 정리

# 입력 받아야 할 값들
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

17일자 글에서 tool 이라는 리스트를 만드는 것까지 정리 했다.

 

# 아직 모르겠는 것:

for _ in range(m): 이 부분에서 왜 m을 넣는 건지 모르겠다.

연습하고 있는 입력 값이 5, 5, 3 이라 n, m값이 같아서 우선 그냥 넘어갔는데, 다른 예제도 넣어보면서 왜 m을 넣었는지 알아내야겠다.  (코드 짜는 데 간선의 갯수가 굳이 왜 필요한 건지 이해를 못하고 있는 상태.)

 

 

이제 dfs를 구현한 코드를 정리해보자. 전체적인 코드는 아래와 같다.

# requirement: stack=[], visited_node=[]
def dfs(s_node, visited_node):
    # visited_node = []       # visited_node = [3,1,2,5,4 ]
    stack = [s_node]          # stack = []

    while stack:
        target_node = stack.pop()
        visited_node.append(target_node)
        for i in range(n+1):    # i = 0 1 2 3 4 5
            if tool[target_node][i] == 1 and i not in visited_node:
                dfs(i, visited_node)

    return visited_node

우선 나한테 필요한 리스트를 2개 만든다.

stack = [ ]

visited_node = [ ]

 

디테일 빼고 큰 틀만 생각하면, stack에는 방문해야 할 숫자를 넣어놓을 것이고, stack에서 pop()해서 pop한 숫자는 방문을 마쳤다는 의미로 visited_node에 넣어둘 것이다.

공부하면서 stack은 대기자 명단, visited_node는 방명록같다는 생각을 했다.

이제 조건을 생각해서 코드를 짜야 하는데, 나는 순차적으로 짤 수가 없어서 에러 뜨면 읽고 고쳐나가면서 코드를 짠다.

 

(n = 5,        m = 5,      start_node = 3)

start_node( == s_node)가 3이니까 3을 스택에 넣자.

>> stack = [3]

 

stack에 값이 있다면 while문 안에 있는 코드를 실행하도록 조건을 설정해주자.

stack에 값이 들어 있지 않다면 ( == stack이 비어있다면) while문을 실행하지 않고 return문을 만나 visited_node를 바로 반환해주게 된다.

stack에 3이 들어 있으니 while문 안으로 들어가면 stack.pop()을 만나 stack에서 3이 삭제가 된다. 그리고 pop된 3은 target_node 변수 안에 담기게 된다.

>> stack = [ ], target_node = 3

 

target_node를 visited_node에 담아둔다. 방문 한 숫자는 visited_node에 담아서 다시 방문하는 일이 없도록 한다.

>> visited_node = [3]

 

이제 for문을 이용해서 tool에 있는 숫자가 1로 돼있는지 확인을 해야 한다. 1로 돼있는 좌표를 만나면 dfs는 바로 그 숫자를 만나러 가야 하기 때문인데, 아...글로는 설명이 안된다. 코드를 보면서 정리하자.

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]]

        for i in range(n+1):    # i = 0 1 2 3 4 5
            if tool[target_node][i] == 1 and i not in visited_node:
                dfs(i, visited_node)

두 개를 같이 놓고 보면 이해가 잘 된다. for문을 실행하면 i의 범위는 0~5이고, 현재 target_node는 3이다.

i가 0일 때 대입을 해보자.

만약 tool[3][0]이 1이고,  0이 visited_node에 담겨 있지 않다면, dfs(i, visited_node)를 실행해야 한다.

tool[3][0] == 0이라 해당 사항이 없어 if문에 걸리지 않게 되고, 다음 순서인 i가 1일 경우를 살펴보면 tool[3][1] == 1이다. 그리고 1은 visited_node에도 담겨 있지 않다.

그렇다면 dfs(1, visited_node)를 실행하게 되는데, 재귀함수이다.

>> i = 1일 때 조건 만족.

visited_node = [3]

dfs(1, visited_node)로 실행. 

 

 

다시 dfs()함수를 실행하며 살펴보자.

# requirement: stack=[], visited_node=[]
def dfs(s_node, visited_node):
    # visited_node = []       # visited_node = [3,1,2,5,4 ]
    stack = [s_node]          # stack = []

    while stack:
        target_node = stack.pop()
        visited_node.append(target_node)
        for i in range(n+1):    # i = 0 1 2 3 4 5
            if tool[target_node][i] == 1 and i not in visited_node:
                dfs(i, visited_node)

    return visited_node

다시 dfs 함수로 돌아왔다. 처음과 달라진 것은 s_node가 3이 아니라 이번엔 1이라는 것이다.

이 1은 stack에 담기게 된다.

>> stack = [1]

 

이번에도 stack엔 값이 있으니까 while문을 실행한다. stack.pop()을 하자. 

>> stack = [ ], target_node = 1

 

이 1을 visited_node에 담아둔다. visited_node에는 방문했던 숫자들이 쌓이게 된다.

>> visited_node = [3, 1]

 

for문을 실행하자. i가 0 ~ 5일 때를 살펴본다. 이번엔 target_node가 1이니 조심하자.

i가 0, 1 일때는 if문 조건에 해당하지 않아 패스 하고, i가 2일 때 조건에 맞으니 살펴보면, tool[1][2] == 1 이고, 2도 visited_node에 없으니 다시 dfs()함수를 실행한다.

>> dfs(2, visited_node)

 

다시 dfs(2, visited_node)를 실행해보자.

이번엔 s_node가 2가 되었다. stack에 s_node를 담아두자.

>> stack = [2]

 

while 조건문을 충족하니 while문 안으로 들어가 코드를 실행하자.

>> stack = [ ], target_node = 2

>> visited_node = [3, 1, 2]

 

 

---

 

이걸 계속 반복하다보면 visited_node = [3, 1, 2, 5, 4 ]가 되고 stack = [ ] 가 된다.

여기에서 다시 while문을 실행하려고 하면, while stack: 조건에 맞지 않게 된다.

 

나는 처음에 while stack: 이런식으로 돼 있는 코드가 무슨 뜻인지 몰랐다.  TRUE, FALSE 이용해서 작성했을텐데, 그럼 코드가 더 길어지고 복잡해졌겠지.

알고리즘 문제를 풀다보니 다양한 사람의 코드를 분석하게 되는데 많은 사람들이 저렇게 코드를 작성하더라.

 

stack이 비어 있는 상태니 while문 조건에 해당하지 않아 while문은 건너뛰고 return문을 실행한다.

visited_node를 반환하면 되니, [3, 1, 2, 5, 4]라는 결과가 나오는데, 그림을 보며 비교해보자.

 

DFS 흐름

제시된 문제는 2와 5가 연결이 돼있어서 3을 시작으로 한바퀴 돌아가는 모양이 됐다.

만일 2와 5가 연결이 되지 않은 상태면, 3 -> 1 -> 2 -> 4 -> 5가 됐을 것이다.

...

한 번 해보고 와야겠다.

 

---

 

 

충격적이네.

재귀함수를 잘 모르니까 여기서 또 막힌다.

2와 5가 연결 돼있지 않다면, tool 은 아래와 같다.

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

DFS로 했을 때 순서가 3 -> 1 -> 2 -> 4 -> 5 라는 건 확실히 알겠는데, 재귀 함수 호출했다가 돌아오는? 부분에서 항상 막힌다.

 

stack = [2] 일 때, pop()하고 나면

>> stack = [ ], visited_node = [3, 1, 2, ]

 

이 상태에서 for문에 들어가면 if문의 조건을 충족하지 못한다.

>> tool[2][1] == 1 이지만 1은 이미 visited_node에 있으니까 if문을 빠져나오고 다시 while stack: 으로 가게 되는데, stack은 비어 있는 상태라서 while문도 못 들어가고 return 해서 visited_node를 반환하게 된다.

그럼 더 돌지도 않고 결과 visited_node = [3, 1, 2]을 반환하고 끝인가, 중간에 잘못 계산했나 싶어서 결과를 돌려봤는데, 결과는 [3, 1, 2, 4, 5]로 잘 나온다.

 

 

디버깅을 하자.

디버깅 했을 때 

visited_node를 반환하는 게 아니라 다시 34번째 코드로 복귀한 다음, target_node = 1인 상태로 32번째 for문을 돌면서 체크하고, 또 다음 target_node = 3인 상태로 for문을 체크하게 된다. (back하고 있는)

target_node = 3일 때, tool[3][1]과 tool[3][4]가 조건에 맞는데, 1은 visited_node에 있으니까 패스 하고, i = 4가 if 문으로 들어가서 dfs(4, visited_node)를 실행하게 된다.

 

 

디버깅하니까 뭐 어렴풋이 알 것 같은데, 잘 모르겠다. 재귀 함수. 

저 다시 돌아가는 시점을 정확히 모르고 있는 것 같은데, 그래서 어렵고... 재귀 함수 피하고 있었는데 안되겠다.

재귀 함수도 공부해서 정리해서 올려야겠다.

 

 

factorial(5) 함수를 생각해보면

>> 5 * factorial(4)

 

factorial(4)

>> 4 * factorial(3)

 

factorial(3)

>> 3 * factorial(2)

 

factorial(2)

>> 2 * factorial(1)

 

factorial(1)

>> 1

 

이렇게 구해놨으면, factorial(5) 했을 때  5 * 4 * 3 * 2 * 1 해야 하는데 돌고 돌아 factorial(1)이 1이니까 '음, return 1', 답은 1.

이러고 있는 상황인가...?

 

 

---

아, 재귀 때문에 잊었네. print하는 함수를 안 적었다.

 

print(" ".join(map(str, dfs(start_node, list()))))

이렇게 하면 백준 문제에서 요구하는 출력값이 나오게 된다.

>> 3 1 2 5 4

 

처음에 단순히 print(dfs(start_node, list())) 이렇게 작성해서 돌렸는데,

>> [3, 1, 2, 5, 4]

이렇게 출력이 됐다.

 

리스트를 어떻게 괄호 없이 출력하는지 찾아보니까

예를 들어 test = [3, 1, 2, 5, 4] 라면 아래와같이 적어주면 test의 문자열만 나오게해준다.

print(" ".join(test))

 

 

가 아니라 타입에러가 뜬다.

TypeError

왜?

test = ["강아지", "고양이", "북극곰"]
print(test)
print(" ".join(test))

# 출력 결과
# ['강아지', '고양이', '북극곰']
# 강아지 고양이 북극곰

리스트의 요소가 문자열이어야 바꿔주기 때문이다. 

 

그렇다면 dfs(start_node, list())를 str타입으로 바꿔주고 출력을 해보자. 

" "사이에 ",  "을 넣으면 ' , '도 같이 출력 해준다. 

 

print(" ".join(map(str, dfs(start_node, list()))))
print(", ".join(map(str, dfs(start_node, list()))))

# 3 1 2 5 4
# 3, 1, 2, 5, 4