[실전 알고리즘] 0x0A강 - DFS

 

드디어 01 02 03 이렇게 숫자를 넘어서 0A강에 도달했습니다. 아직 완결까지는 한참 남았지만 아무튼 힘을 내서 계속 잘 해봅시다. 아, 참고로 저번 단원보다는 내용이 많지 않아서 편한 마음으로 들으실 수 있을 것입니다.

 

보시면 BFS에서는 끝도 없이 많았던 응용 파트가 여기서는 싹 사라진걸 볼 수 있습니다. 왜 그런건지는 천천히 같이 알아가도록 하겠습니다.

 

일단 DFS의 정의는 다차원 배열에서 각 칸을 방문할 때 깊이를 우선으로 방문하는 알고리즘입니다. 참고로 BFS는 깊이 대신 너비를 우선으로 방문하는 알고리즘이었습니다. 깊이나 너비나 모호한건 매한가지일거니 이번에도 마찬가지로 실제 예시를 보면서 DFS의 과정을 이해해야 할 것 같습니다.

 

과정을 먼저 소개해보면 뭔가 어디서 본 것 같다는 느낌을 받을텐데, 바로 BFS의 과정에서 딴건 다 똑같고 큐만 스택으로 바뀐 것 뿐입니다. 큐를 쓰면 BFS이고 스택을 쓰면 DFS가 됩니다. 이번에는 DFS로 상하좌우로 나와 인접한 같은 색의 칸을 방문하는 Flood Fill을 해결해보겠습니다.

 

이번에도 (0, 0)과 상하좌우로 이어진 모든 파란색 칸을 확인해보도록 하겠습니다.

 

우선 (0, 0)에 방문했다는 표시를 남기고 해당 칸을 스택에 넣습니다. 이게 초기세팅이고 이후에는 스택이 빌 때 까지 계속 스택의 top을 빼고 해당 좌표의 상하좌우를 살펴보면서 스택에 넣어주는 작업을 반복하면 됩니다.

 

지금 스택의 top은 (0, 0)이고 pop을 합니다. 그리고 (0, 0)의 상하좌우 칸을 보는데, 이 중에서 우리는 파란색 칸이면서 아직 방문하지 않은 칸을 찾을 것입니다.

 

보면 (0, 1)과 (1, 0)이 모두 파란 칸이면서 아직 방문하지 않은 칸이니 방문했다는 표시를 남기고 스택에 넣습니다.

 

이미 BFS에서 한 번 본 내용이라 더 설명을 안해도 될 것 같긴 하지만 이왕 시작한거 조금만 더 같이 해보겠습니다. 지금 스택의 top은 (1, 0)이고 pop을 하겠습니다. 상하좌우 칸들을 확인해보면 (0, 0)은 파란 칸이지만 이미 방문을 했고, (1, 1)은 빨간 칸입니다. 유일하게 (2, 0)만 파란색 칸이면서 아직 방문하지 않은 칸이니까 (2, 0)에 방문했다는 표시를 남기고 스택에 넣습니다.

 

이후의 진행은 설명 없이 사진으로 보여드리겠습니다.

 

이렇게 스택이 비는 순간 과정은 종료됩니다. DFS도 BFS처럼  Flood Fill이 필요할 때 사용할 수 있음을 알 수 있습니다. 그런데 보면서 느끼셨을지 모르겠지만 BFS와 DFS 모두 비록 최종적인 방문 결과는 똑같더라도 방문 순서에서 아주 큰 차이가 있습니다. 이 부분은 다음 챕터에서 BFS와 DFS를 비교할 때 제대로 설명을 드리겠습니다.

 

DFS를 구현한 코드를 보면 굉장히 익숙할 것입니다. BFS 코드에서 큐만 스택으로 바꾼 것 뿐입니다. 코드에 대한 설명은 이미 BFS 단원에서 충분히 했기 때문에 여기서 또 하지는 않겠습니다. 이전 단원을 듣지 않고 그냥 DFS를 찾다가 이 강의를 접하게 됐는데 코드에 의문점이 있다면 0x09강 - BFS를 참고하시면 됩니다. (깃헙 링크)

 

이렇게 BFS와 DFS를 살펴보면 BFS는 큐를 쓰고 DFS는 스택을 쓴다는 차이가 있지만 원소 하나를 빼내고 주변을 살펴본다는 알고리즘의 흐름은 똑같습니다. 하지만 둘의 방문 순서는 큰 차이가 있는데 우선 BFS에서의 방문 순서를 확인해보겠습니다. 시작점을 중앙으로 잡았는데 보면 마치 냇가에 던진 돌로 인해 동심원이 생기는 것 처럼 상하좌우로 퍼져나가는 것을 볼 수 있습니다. 그리고 이전 단원에서 다룬 BFS의 성질인 거리 순으로 방문한다는 것 또한 잘 성립함을 알 수 있습니다. 이번에는 DFS에서의 방문 순서를 확인해보겠습니다. 이건 어떻게 비유를 해야할지 모르겠긴 한데 아무튼 뭔가 차이가 있다는건 알 수 있을 것입니다. 뭔가 한 방향으로 막힐 때 까지 쭉 직진을 한다는걸 알 수 있습니다. 지금 보신 것과 같이 BFS와 DFS는 방문 순서에 큰 차이가 있습니다.

 

그리고 BFS에서 유용하게 썼던 "현재 보는 칸으로부터 추가되는 인접한 칸은 거리가 현재 보는 칸보다 1만큼 더 떨어져있다"는 성질이 DFS에서는 성립하지 않습니다. 이 그림은 (0, 0)에서 DFS를 시작할 때 나오는 상황인데, 빨간색 칸은 거리가 4인 반면 검정색 칸은 거리가 3입니다. 그래서 거리를 계산할 때에는 DFS를 사용할 수 없습니다. 그러면 결국 우리는 다차원 배열에서 굳이 BFS 대신 DFS를 써야하는 일이 없습니다. Flood Fill은 BFS와 DFS 중에서 어느 것을 써도 상관없는데 거리 측정은 BFS만 할 수 있으니 BFS 대신 DFS를 쓸 일이 없습니다. 그래서 앞으로 다차원 배열에서 순회하는 문제를 풀 때 계속 BFS만 짜게 됩니다. 하지만 그렇다고 해서 DFS가 아예 무쓸모한건 아니고 나중에 그래프와 트리라는 자료구조를 배울 때 DFS가 필요하게 됩니다. 그러니 아예 잊어버리지는 마시고 DFS는 스택을 써서 다차원 배열의 순회를 처리하는 알고리즘이다, 깊이를 우선해서 탐색한다는데 깊이가 무슨 의미인지는 아직 잘 와닿지 않는다 정도로만 기억하고 넘어가면 이번 단원에서 해야할 내용은 다 했습니다.

 

이로써 다차원 배열에서의 BFS와 DFS를 해결했습니다. 앞 슬라이드에서 열심히 설명했지만 굳이 BFS말고 DFS로 풀어야 하는 문제가 있지 않아서 따로 이번 단원과 연계되는 문제를 두지는 않았습니다. BFS 파트의 문제를 마저 푸시면 됩니다. 다음 단원은 재귀인데 재귀에서 어려움을 겪는걸 많이 봤어서 조금 걱정이 됩니다. 재귀를 한 번쯤은 들어보셨을테지만 막상 그걸 가지고 문제를 풀려고 하면 정말 까다로울 수 있습니다. 그러니까 다음 강의를 듣기 전에 재귀의 기본적인 개념이라도 한 번 보고 오시면 좋겠습니다. 예를 들어 재귀로 N부터 1까지 출력하기 내지는 1부터 N까지의 합 구하기 이런 문제를 풀어보면서요. 그럼 다음 시간에 만납시다.

 

  Comments
  • 4분 40 - 47 초 버퍼걸린줄 알았어요 ㅋㅋ

    그리고 재귀 기본 문제중에서
    재밌는 문제를 찾았는데 https://www.acmicpc.net/problem/17478 요거 괜찮은거같아요
  • Sait2000
    왜 스택인가 했는데 아직 재귀를 안 했군요 ㄷㄷ
  • 바쁘신가운데 올려주셔서 감사합니다 ㅠㅠ
  • Kim
    감사합니다.!!
  • 익명
    비밀댓글입니다
  • 익명
    비밀댓글입니다
    • 1. 주어진 모든 점들을 정렬합니다. 정렬할 때 각 점이 시작점인지 끝점인지 알고있어야 합니다.

      예를 들어 (1, 6), (2, 3), (7, 15), (14, 18)이면 1s 2s 3e 6e 7s 14s 15e 18e로 정렬합니다.

      2. 점들을 앞에서부터 읽어나면서 내부적으로 0으로 초기화된 cnt라는 변수를 두어 s는 +1을, e는 -1을 합니다. cnt가 0이 되는 순간이 잘 생각해보면 수직선이 분리되는 곳임을 알 수 있고 적절하게 처리를 해주면 선분이 N개 주어져있을 때 O(NlgN)에 처리가 가능합니다.

      대략적인 느낌은 이정도인데 중복된 점이 있을 때 전부 모아서 처리를 해줘야합니다.

      https://www.acmicpc.net/problem/2170 이 문제를 보시면 도움이 될 것 같습니다.
    • ㄹㄹㄹ
      아 좋은 방법이네요 정말 감사합니다!! 도움 많이 될 것 같습니다. 그리고 늘 강의 감사합니다! 이 블로그 고파스에서 보고 왔거든요ㅋㅋㅋ
  • ㅇㅇ
    감사합니다 혹시 pdf 자료는 따로 업로드 안해주시는건가요...?
  • 익명
    비밀댓글입니다
  • dfsbfs 질문
    "굳이 BFS말고 DFS로 풀어야 하는 문제가 있지 않아서 따로 이번 단원과 연계되는 문제를 두지는 않았습니다. BFS 파트의 문제를 마저 푸시면 됩니다." -> 이 말씀은 bfs만 능숙하게 사용할줄알면 된다는 말씀인가요? 따로 구분없이 전부 bfs로 풀면 되는건지 궁금합니다.
  • DFS와 BFS에 대해서 궁금한게 있어서 댓글 답니다.
    DFS와 BFS 모두 설명 하실 때
    시작하는 칸을 스택(큐)에 넣고 방문 했다는 표시를 남김이라고 설명하셨는데

    실제 코드를 보면(DFS기준)
    vis[0][0] = 1;
    S.push({0,0});
    이렇게 하셨는데 그럼 시작하는 칸을 방문 했다는
    표시를 남기고 스택에 넣다라고 해야되는거 아닌가요?
    아니면 둘이 그냥 똑같나요?
    순서가 바뀌어도 전혀 지장 없는건가요?


    • 서로 다른 두 변수 a, b에 각각 3과 5를 더해야 한다 치면

      a+=3;
      b+=5; 로 하나

      b += 3;
      a += 5; 로 하나 결과는 동일하죠

      같은 관점에서 시작하는 칸을 스택(큐)에 넣고 방문 했다는 표시를 남기나 방문했다는 표시를 남긴 후 스택에 넣으나 결과는 당연히 똑같아요

      다만 혼동을 막기 위해서

      S.push({0,0});
      vis[0][0] = 1;

      으로 코드를 써놓을걸 그랬네요
  • 킹갓독
    '(2,0)에 남기고 큐에 넣습니다' 부분 오타 있어요! 큐가아니라 스택이여
  • 갓킹독
    백준 13549에서
    두 코드의 차이를 모르겠습니다 단지 순서만 바뀐건데 하나는 맞고 하나는 틀렸습니다가 뜹니다..!


    1) 틀렸습니다
    #include <bits/stdc++.h>
    using namespace std;

    int arr[200002];
    int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n,m;
    cin>>n>>m;

    queue<int> Q;
    Q.push(n);
    arr[n]=1;



    while(arr[m]==0){
    int a = Q.front(); Q.pop();


    for( auto c: {a-1, a+1}){
    if(c<0 || c>100000) continue;
    if(arr[c]!=0) continue;
    arr[c]=arr[a]+1;
    Q.push(c);

    }

    if(2*a <= 100000 && 2*a!=0){
    arr[2*a]=arr[a];
    Q.push(2*a);
    }



    }

    cout<<arr[m]-1;

    return 0;
    }


    2) 맞았습니다

    #include <bits/stdc++.h>
    using namespace std;

    int arr[200002];
    int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n,m;
    cin>>n>>m;

    queue<int> Q;
    Q.push(n);
    arr[n]=1;



    while(arr[m]==0){
    int a = Q.front(); Q.pop();

    if(2*a <= 100000 && 2*a!=0){
    arr[2*a]=arr[a];
    Q.push(2*a);
    }
    for( auto c: {a-1, a+1}){
    if(c<0 || c>100000) continue;
    if(arr[c]!=0) continue;
    arr[c]=arr[a]+1;
    Q.push(c);

    }

    }

    cout<<arr[m]-1;

    return 0;
    }
댓글 쓰기