디스 프로그래머 (This Programmer)

[백준/1260/파이썬3(python3)] DFS와 BFS 본문

알고리즘/풀이

[백준/1260/파이썬3(python3)] DFS와 BFS

디스 프로그래머 2019. 2. 16. 19:43

[백준/1260/파이썬] DFS와 BFS

문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

입출력 예

입력출력
4 5 1
1 2
1 3
1 4
2 4
3 4
1 2 4 3
1 2 3 4

개념

내가 처음 만나게 된 그래프 탐색 문제이다. DFS가 뭔지, BFS가 뭐지도 몰랐던 상태에서 만나게 된 문제라 굉장히 당혹스러웠지만 읽어보니 예전에 정보처리기사 땄을 때 공부한 거였다. 이제부터 이 문제를 풀기 위해 알아야 할 개념들을 하나씩 나열해보겠다.

  1. DFS는 깊이우선탐색(Depth First Search)이고 BFS는 너비우선탐색(Breadth First Search)를 의미한다.

  2. 위 입력으로 주어진 그래프를 이해하기 쉽게 그려보면 다음과 같다.


    생각없이 그리다가 이런 모습들이 되었지만... 

    이게 합리적이고 납득할 수 있는 모습일 것이다.

  3. 출력을 보면 알 수 있다시피 DFS는 다음과 같은 과정으로 탐색이 진행되었다.

    말 그대로 제일 깊은 곳까지 내려갔다가 다시 분기점으로 올라와서 가지 않았던 길을 다시 가보는 식의 탐색방법이라고 보면 되겠다.

  4. 마찬가지로 BFS는 다음과 같은 과정으로 탐색이 진행되었다.


  5. 위에 주어진 노선도를 코드로 구현하려면 "인접행렬(Adjacency Matrix)"이라는 것을 알아야 한다. 인접행렬이란 자료형의 일종으로 그래프 이론에서 어느 노드들끼리 연결되었는지를 나타내는 이차원 행렬을 의미한다. 그림으로 그려져있는 저 트리를 컴퓨터가 이해할 수 있게 만들어주는 과정이라고 보면 될 것이다.

     1234
    10111
    21001
    31001
    41110

    정석으로 그리자면 다음과 같은 모습이다. 1번은 2, 3, 4와 연결돼있으므로 1번 행과 열의 2, 3, 4에 해당하는 칸에 1이라고 적혀있다. 바깥쪽 범례(1,2,3,4)를 제하고 0과 1로만 이뤄진 부분이 인접행렬이다. 코드로 보자면 이런 모습이라 할 수 있겠다.

    adjacency_matrix = [[0, 1, 1, 1],
                        [1, 0, 0, 1],
                        [1, 0, 0, 1],
                        [1, 1, 1, 0]]
    

    하지만 코드상 배열의 시작은 항상 0이기 때문에 위 코드로 그래프를 구현하면 노드1번을 인덱스 0으로, 2를 1로, 3을 2로(and so on-) 표현해야해서 혼동이 일어나기 쉬우므로 대게 코드상 인접행렬을 구현할 땐 index를 그대로 value로 가져가는 경우가 많다. 그러니까 결국 이런 모습이 되는 것이다. 테이블로 구현했을 땐

     01234
    000000
    100111
    201001
    301001
    401110

    코드로 구현했을 땐

    adjacency_matrix = [[0, 0, 0, 0, 0],
        				[0, 0, 1, 1, 1],
                        [0, 1, 0, 0, 1],
                        [0, 1, 0, 0, 1],
                        [0, 1, 1, 1, 0]]
    

    이 되는 것이다. 이러면 인덱스와 벨류가 딱 맞아 떨어져 구현하기 쉬워진다. 이제 위 추상적인 노드 그림을 2차원배열로 구현할 수 있게 되었으니 본격적으로 코드를 통해 탐색방법을 구현해보자.

풀이

N, M, V = map(int, input().split())
matrix = [[0] * (N + 1) for _ in range(N + 1)]
for _ in range(M):
    link = list(map(int, input().split()))
    matrix[link[0]][link[1]] = 1
    matrix[link[1]][link[0]] = 1


def dfs(current_node, row, foot_prints):
    foot_prints += [current_node]
    for search_node in range(len(row[current_node])):
        if row[current_node][search_node] and search_node not in foot_prints:
            foot_prints = dfs(search_node, row, foot_prints)
    return foot_prints


def bfs(start):
    queue = [start]
    foot_prints = [start]
    while queue:
        current_node = queue.pop(0)
        for search_node in range(len(matrix[current_node])):
            if matrix[current_node][search_node] and search_node not in foot_prints:
                foot_prints += [search_node]
                queue += [search_node]
    return foot_prints


print(*dfs(V, matrix, []))
print(*bfs(V))

설명

최대한 직관적으로 읽을 수 있게 작성하였다. 비어있는 매트릭스에 주어진 그래프로 인접행렬을 생성하고 DFS방식과 BFS방식으로 탐색한다. DFS방식은 간선이 연결돼있는 노드를 발견하면 다시 또 DFS방식으로 탐색을 시작하는 재귀형식으로 구현되었다. 정확한 흐름을 파악하고 싶다면 주어진 예제에서 DFS방식과 BFS방식의 분기점이 생기는 2번 노드에서의 흐름을 직접 읽어보는 게 좋다.

 

 

P.S : 처음 풀어보는 그래프 문제여서 공부할 게 많았다. 사실 백준 알고리즘을 풀 때 사람들이 많이 풀었지만 나는 아직 풀지 못 한 문제를 순서로 푸는데 이 문제 때문에 다소 지체됐었다. 알아야할 게 많으니 괜히 하기 싫어져서말이다. 뭔가 스스로를 채찍질하는 계기가 됐다. 그리고 맨날 같은 일을 하는 요즘 오랜만에 머리써서 자극이 되고 재미있었다.

13 Comments
  • 프로필사진 지나가던초보 2019.04.04 22:02 궁금한게 있는데 입력을 받을 때

    첫번째는
    N, M, V = map(int, input().split()) 이렇게 받았는데

    두번째는
    link = list(map(int, input().split())) 이렇게 list를 한번더 감싸는 이유가 뭔가요?
  • 프로필사진 Favicon of https://this-programmer.com 디스 프로그래머 2019.04.05 12:30 신고 link변수에 담기는 건 각 노드들끼리의 연결 정보, 곧 인접행렬에 값을 채우는 값들이라고 할 수 있는데 이를 쉽게 채우려고 한 것입니다. 실제로도 link로 입력받는 값은 바로 밑 두줄에서밖에 안쓰이죠?

    입력값에서 주어지는 N, M, V은 각각 다른 의미를 갖고 있습니다. 그 아래의 노드 연결정보가 (1 2, 1 3, 1 4등) 일관성있는 형태라는 걸 의미하려 의도한 것입니다. 꼭 list로 감싸지 않고 N, M, V형태처럼 start_node, destination_node = map(int, input().split()) 형태로 받으신 다음에 link[0]이 들어갈 자리에 start_node, link[1]이 들어갈 자리에 destination_node로 채우셔도 괜찮습니다!

    생각해보니 이게 오히려 더 직관성있는 변수명이겠네요. 질문 감사드립니다!
  • 프로필사진 지나가던촙호 2019.05.01 12:16 dfs 함수 부를때 *를 붙이는데 *는 어떤의미인가요?
  • 프로필사진 Favicon of https://this-programmer.com 디스 프로그래머 2019.05.01 14:07 신고 list나 set등 컨테이너형의 자료를 풀 때 사용하는 연산자입니다.
    편의상 맨 마지막 줄에 dfs와 bfs의 앞에 *을 붙였는데 두 함수 모두 리턴값이 리스트형태인 걸 확인하실 수 있습니다. 만약에 함수의 결과값을 이 문제에서 요구하는 대로 출력하기 위해선 그냥 변수에 담아서 print하는 것이 아닌 for문 등을 통해 해당 리스트를 전부 순회하며 출력해야 하는데 이 과정을 줄여줍니다.
    아래 링크의 4번을 참조하시면 이해가 쉬우실 겁니다!
    https://mingrammer.com/understanding-the-asterisk-of-python/#4-%EC%BB%A8%ED%85%8C%EC%9D%B4%EB%84%88-%ED%83%80%EC%9E%85%EC%9D%98-%EB%8D%B0%EC%9D%B4%ED%84%B0%EB%A5%BC-unpacking-%ED%95%A0-%EB%95%8C

  • 프로필사진 Favicon of https://zeezlelove.tistory.com 파이썬 잘하고 싶다. 2019.05.12 20:09 신고 안녕하세여 dfs공부하고있는 중1입니다;;.. 짐 첨배우는데 어떻게 하면 디스프로그래머님처럼 파이썬을 잘할수있을까요.. dfs는 도저히 머리가 돌아가지 않아서요..
  • 프로필사진 Favicon of https://this-programmer.com 디스 프로그래머 2019.05.13 08:11 신고 저도 배워가는 입장이라 뭔가 해답을 제시할 수는 없는 입장이에요... ㅋㅋㅋ
    하지만 제가 예전에 읽었던 책에서 나왔던 말을 인용하자면 아무리 머리를 많이 쓰는 학문이나 기술일 지라도 읽고 생각하는 것만으로는 절대로 늘지가 않는다는 말이었어요. 프로그래밍을 배우는 거나 수영을 배우는 거나 다름 없다고 생각합니다.
    좋은 모델을 목표로 두고 꾸준히 만들어보고 실패해보고 반성하고 피드백하고, 이런 일련의 과정들이 실력향상에 큰 도움이 될 것 같습니다!
  • 프로필사진 airplane2230 2019.06.18 03:04 도움이 많이 됩니다!
  • 프로필사진 학식 2020.01.27 23:00 안녕하세요 질문이 하나 있는데 dfs알고리즘에서 foot_prints = dfs()
    여기서 foot_prints = 이걸 꼭 해줘야하나요? 저거 빼도 똑같이 작동하는데 이유가 궁금합니다..
    그리고 디스 프로그래머님은 지금 하시는 일이 무엇인지도 가르쳐주실수있나요?
  • 프로필사진 Favicon of https://this-programmer.com 디스 프로그래머 2020.01.28 17:43 신고 dfs함수가 재귀형식으로 쓰여지고 있기 때문에 current_node가 포함되어 만들어진 foot_prints변수가 그대로 매개변수로 들어가서 사실상 필요 없는 부분이 맞았네요! 날카로우신 질문 덕분에 하나 더 배우게 됩니다. 감사합니다.

    아, 그리고 전 현업 프로그래머입니다!
  • 프로필사진 학식 2020.01.29 23:38 현업에서 파이썬을 주로 사용하시나요? 웹개발자이신지 어떤 분야인지 궁금해요!
  • 프로필사진 Favicon of https://this-programmer.com 디스 프로그래머 2020.01.30 02:02 신고 웹개발자이며 현업에서는 주로 php를 씁니다. 하지만 알고리즘 공부는 파이썬으로 했어가지고 파이썬을 병행하며 공부하고 있고 개인프로젝트를 django로 준비하고 있으며 다음 회사는 python/django를 사용하는 회사로 갈 예정이에요!
  • 프로필사진 학식 2020.02.01 16:19 저도 장고 관심있었는데 지금은 udemy 웹개발통합 강의듣고있는데 여기서는 nodejs라 그냥 nodejs먼저 배우고있는데요
    혹시 장고를 선택하신 이유를 알 수 있을까요?
  • 프로필사진 Favicon of https://this-programmer.com 디스 프로그래머 2020.02.01 23:30 신고 웹개발 뿐만 아니라 머신러링, AI등의 분야에도 관심이 있는데 구글에서 만든 텐서플로우가 파이썬 언어를 기반으로 해서 관심이 생겼다가 간결한 문법에 반해서 알고리즘 공부를 파이썬으로 시작하고, 제가 일하는 분야인 웹개발을 파이썬으로 할 수 있는 방법이 없나? 했는데 딱 쟝고가 있더라구요.

    쉽고 간결하고 개발속도도 빠르고 해서 결국엔 쟝고로 정착했습니다. 제가 쓴 게시물 중에
    https://this-programmer.com/entry/%EC%97%AC%EB%9F%AC%EA%B0%80%EC%A7%80-%EC%96%B8%EC%96%B4%EC%99%80-%ED%94%84%EB%A0%88%EC%9E%84%EC%9B%8C%ED%81%AC%EB%93%A4%EC%9D%84-%EC%8D%A8%EC%98%A4%EB%A9%B0-%EB%8A%90%EA%BC%88%EB%8D%98-%EB%8B%A8%EC%83%81

    로 들어가보시면 여러가지 언어와 프레임워크를 써오면서 느꼈던 점들이 있는데 읽어보시면 도움이 될 거에요!
댓글쓰기 폼