BaaaaaaaarkingDog
코딩, 해킹
[실전 알고리즘] 0x05강 - BFS, DFS

[실전 알고리즘] 0x05강 - BFS, DFS.pdf


이번 시간엔 코딩테스트 단골 유형인 BFS, DFS에 대해 알아보겠습니다.



시작하기에 앞서, 원래는 0x03장에서 언급했던 전위 중위 후위 표기식을 먼저 다루려고 했습니다. 해당 내용은 학부 자료구조에서 스택을 배울 때 거의 대부분 짚고 넘어가는 내용이기 때문입니다. 그러나 표기식이 난이도도 어렵고 요구되는 구현력도 다소 높은 것에 비해 다소 지엽적인 내용이기 때문에 코딩 테스트와 면접에 나올 확률은 0에 가깝다고 판단, 이 내용을 실전 알고리즘 강의에서 다루지 않기로 결정했습니다.


그러나 삼성 역량 테스트 B형 정도의 수준에는 충분히 나올 수 있는 내용이니 본인이 알고리즘을 더 깊게 공부하고 싶다면 여유가 있을 때 직접 찾아서 공부를 해보세요.


플러드필은 다차원 배열에서 어떤 칸과 연결된 영역을 찾는 알고리즘입니다. 마치 그림판에서 색 채우기 명령으로 동일한 색을 전부 바꿔버리는 것과 동일합니다.


플러드 필 문제는 DFS/BFS 알고리즘으로 해결할 수 있습니다. 플러드 필은 적당한 난이도의 자료구조 지식과 구현력을 요구하는 문제이기 때문에 코딩테스트에 정말 자주 나오는 유형입니다. BFS는 큐로 구현할 수 있고 DFS는 스택으로 구현할 수 있습니다.


BFS는 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘입니다. 너비라니.. 잘 이해가 안가시죠? 정상입니다. 원래 BFS와 DFS는 그래프 자료구조에서 모든 노드를 방문하기 위한 알고리즘으로, 다차원 배열이 그래프 자료구조의 특수한 형태이기 때문에 다차원 배열에서도 BFS, DFS를 사용할 수 있는 것입니다.


그렇기에 BFS와 DFS를 정확하게 이해하려면 그래프 자료구조에 대한 이해가 선행되어야 하나 그건 배보다 배꼽이 커지는 느낌입니다. 대신 구체적인 알고리즘을 보면서 다차원 배열에서의 BFS를 이해해봅시다.


BFS 과정을 글로 풀어적으면 간단합니다.


이 과정에서 모든 칸이 큐에 1번씩만 들어감이 보장되므로 시간복잡도는 칸이 $N$개일 때 $O(N)$입니다. 직접 예시를 보면서 이해해봅시다.


(0, 0)에서 시작합니다.





















예시가 잘 이해가시나요?


BFS를 실제로 구현하기 위해 큐에 int 2개를 묶은 원소가 들어가야 합니다. 이 부분을 처리하기 위해 STL의 pair를 활용했습니다. 구현 코드를 확인해보세요. 


현재 코드는 BFS 알고리즘으로 Flood Fill을 수행할 수 있습니다. 이외에 BFS를 응용할 수 있는 부분들에 대해 알아보겠습니다. 첫 번째 문제는 BOJ 1926번: 그림입니다. 이 문제를 풀기 위해서는 (0, 0)에서 시작해 BFS를 돌고 끝나는 것이 아니라 이중 for문을 돌면서 아직 방문하지 않은 시작점들을 계속 찾아서 Flood Fill을 수행해야 합니다. 그리고 넓이를 구하기 위해서는 각 시작점에 내부적인 변수를 두어 큐에서 원소를 꺼낼 때 마다 그 변수를 1 증가시키면 됩니다. 정답 코드를 확인해보세요.


두 번째 문제는 BOJ 2178번 : 미로 탐색입니다. 이 문제는 미로의 좌측 상단이 시작점이고 우측 하단이 끝점일 때 시작점에서 끝점으로 가는 최단 경로의 길이를 찾는 문제입니다. 놀랍게도 BFS를 이용해 시작점에서 연결된 다른 모든 점으로의 최단 경로를 찾을 수 있습니다. 이 성질을 이해하기 위해 BFS의 과정을 다시 살펴봅시다.


뭔가 시작점 (0, 0)에서부터 퍼져나가는 느낌이 들지 않나요? (0, 0)에서부터의 거리를 적어보면 더욱 명확해집니다. 현재 보는 칸으로부터 추가되는 인접한 칸은 반드시 현재 보는 칸 보다 시작점으로부터 1만큼 더 떨어져 있습니다.


이 강의에서 해당 성질을 증명하지는 않지만, 귀납법으로 증명이 가능합니다. 이제 이 성질을 이용해 시작 점과의 거리를 계산할 dist 배열을 하나 둠으로서 시작 점에서 다른 모든 점으로 가는데 필요한 거리를 계산할 수 있습니다.


dist 배열을 미리 -1로 초기화 시켜두면 굳이 vis 배열을 따로 둘 필요 없이 dist 배열의 값이 0 이상인지를 가지고 방문 여부를 확인할 수 있습니다.(정답 코드)


BFS의 구현에서 실수를 할 여지가 굉장히 많습니다. 코드를 직접 짜봤는데 답이 나오지 않을 경우에는 이런 상황들을 확인해보세요.


두 번째로 살펴볼 알고리즘은 DFS입니다. DFS는 다차원 배열에서 각 칸을 방문할 때 깊이를 우선으로 방문하는 알고리즘입니다. BFS처럼 이해가 안가는건 똑같네요. BFS와 흐름은 거의 동일하나 큐 대신 스택을 쓴다는 차이점만 있습니다. 역시 구체적인 알고리즘을 보면서 다차원 배열에서의 DFS를 이해해봅시다.


보다시피 BFS와 DFS는 큐에서 원소를 넣었다가 꺼내는지, 스택에서 원소를 넣었다가 꺼내는지에 대한 차이밖에 없습니다. 다시 한 번 직접 예시를 보면서 이해해봅시다.



























마찬가지로 STL의 pair를 이용해 작성된 예시 코드입니다. 단 출력되는 방문 순서는 상/하/좌/우 중 어디를 먼저 스택에 넣냐에 따라 다를 수 있습니다. (2019-01-06에 두두님이 오류를 알려주셔서 수정했습니다. 감사합니다!)


BFS와는 다르게 DFS에서는 현재 보는 칸으로부터 추가되는 인접한 칸은 현재 보는 칸 보다 시작점으로부터 1만큼 더 떨어져있다는 성질이 성립되지 않습니다. 그렇기 때문에 시작점으로부터의 거리를 잴 때는 DFS 대신 BFS를 사용해야 합니다.


그렇기에 다차원 배열에서 DFS는 딱히 쓸 일이 없습니다. 어차피 Flood Fill은 BFS에서도 할 수 있고, DFS에서는 시작 점에서 다른 모든 점으로의 거리를 잴 수 없기 때문입니다. 그러나 나중에 그래프를 배우고 난 뒤에 DFS를 사용해야 하는 상황이 생기므로 DFS에 대한 개념은 가지고 있는 것이 좋습니다.


Flood FIll / BFS / DFS 관련 문제는 코딩테스트 뿐만 아니라 정보올림피아드에서도 워낙 자주 나오는 유형이라 BOJ에 정말 끝도 없이 쌓여 있습니다. 그 중에서 그래프 개념이 필요없는 문제들을 뽑아 그룹에 난이도 순으로 담아두었으니 꾸준하게 풀어보세요.


코딩테스트에 단골로 출제되는 유형이기 때문에 반복 숙달을 통해 코드의 흐름을 손에 익히는 것이 중요합니다.


이번 강의에서 Flood Fill / BFS / DFS를 익혔고, BFS의 응용 사례들과 자주 실수하는 부분을 살펴보았습니다.


  Comments
  • 코린이
    강의 항상 감사합니다! DFS 에서는 시작점부터의 거리를 왜 못재는지 조금 자세히 설명해주실수 있나요? 이해가 잘 안되서요....ㅠㅠ
    • BFS에서는 현재 보고 있는 칸 까지의 거리를 d라고 한다면 현재 보고 있는 칸(주황)으로부터 찾아지는 새로운 칸(초록)들은 거리가 무조건 d+1이에요.

      그런데 DFS에서는 54p나 56p에서 볼 수 있듯이 현재 보고 있는 칸까지의 거리는 4인데 그 칸으로부터 찾아진 칸까지의 거리는 5가 아니라 3이라거나, 현재 보고 있는 칸까지의 거리는 3인데 그 칸으로부터 찾아진 칸 까지의 거리는 4가 아니라 2라던가 하는 일이 생겨서 DFS로는 거리를 재는데 사용할 수 없어요.

      직접
      ooooo
      oxxxxo
      oxxxxo
      oxxxxo
      ooooo

      여기서 DFS와 BFS를 한번 돌려보시면 이해가 더 쉽게 될 수도 있어요.
  • 감사합니다!
    이 강의를 보고 BFS와 DFS에 대한 개념이 잡히는것 같습니다! 좋은 강의 감사합니다.
  • BFS
    좋은 강의 감사합니다. 근데 BFS를 구현할 때 큐에 넣을 때 방문했다고 체크해야 하는 이유가 있나요 ? 바킹독님의 BFS 구현 코드중에서 auto cur = Q.front(); Q.pop(); 이 부분에서 팝하기 전에 방문했다고 체크해주고 팝하면 안되나요 ?
    • pop하기 전에 방문했다고 처리를 하면 큐 안에 동일 원소가 여러 번 삽입되어 비효율적으로 동작할 수 있습니다.

      그렇기에 pop하기 전에 방문했다고 처리를 하면 안되지만, 그렇게 했다고 가정을 할 때 만약 cur = Q.front(); 를 한 이후 cur가 방문한 원소인지를 한번 더 체크한다면 조금 더 비효율적인 O(N)이지만, 체크하지 않는다면 O(N!)이 되어버립니다.

      2번째 문단이 잘 이해가 가지 않는다면 그냥 1번째 문단 내용만 이해하시면 될 것 같아요.
  • ssss
    그룹 링크좀 가능할까요?
  • sankim
    DFS를 스택으로 구현하는건 문제가 없는데
    재귀로 구현하려니까 많이 힘드네요
    제가 재귀가 약해서 그런것 같습니다.

    백트래킹같은 경우 DFS + 가지치기로 알고있는데 이를 재귀로 구현하지 않고 스택으로 구현하면 어떤 단점들이 있을까요?
    • 백트래킹을 스택으로 구현해도 아무 상관이 없습니다. 재귀로 구현한 것과 스택으로 구현한 것을 비교해보면

      1. 함수 호출은 다소 비용이 큰 연산이기 때문에 재귀로 구현하는 것이 스택으로 구현한 것 보다 시간, 메모리 모두 더 사용합니다.

      2. 그러나 백트래킹의 경우, 재귀를 이용하면 스택을 사용한 것 보다 코드가 더 깔끔해지는 경우가 많습니다.

      코드가 깔끔해진다는 장점으로 인해 재귀에 익숙해지는게 좋지만 아무리 해도 익숙해지지 않는다면 이해를 나중으로 미루고 그냥 스택으로 계속 구현하셔도 됩니다.
    • sankim
      감사합니다 ㅠㅠ
      코딩테스트가 다가오는데 재귀때문에 진도를 못나가고 있었거든요 ㅠㅠ
      테스트 마무리 짓고 재귀를 다시 제대로 파보겠습니다!
    • 재귀가 좀 거지같긴 하죠ㅎㅎㅠㅠ 제 글이나 다른 분들 글 보면서 잘 이해해보세용
  • underbar
    감사합니다. 정말 많이 배우고있습니다.
    다만, BFS에서 "미로탐색" 문제의 답안 예시 링크가 "그림" 문제의 링크로 연결되네요.
    워낙 비슷한 문제라서 말씀해주신대로 해결했는데, 저 같은 경우는 문제의 조건중
    배열의 성분은 "붙어서" 입력된다는 부분이 쉽지 않았습니다.
    결국 scanf("%1d,&board[i][j]) 이런식으로 해결하였는데, 어떤식의 풀이를 추천하시나요!?
  • 재민
    바킹독님 사랑해요
  • 좋은 강의 감사합니다! 1과부터 차근차근 보고 문제를 풀어나가고 있습니다. 설명을 너무 잘해주시고 실용적인 Tip들이 정말 주옥같아서 코딩문제 연습하는데 큰 도움이 되고 있습니다. 끝까지 정주행 하도록하겠습니다!
  • quu
    안녕하세요!! 유익한 강의 정말 감사드려요 !!!
    강의 따라하다가 백준 1926 그림 문제에서 최대값을 찾기위해 벡터에 넣은다음에 *max_element로 최대값을 찾는 방식으로 구현을 해보았는데요 런타임 에러가 뜹니다 ㅜㅜ 그래서 정석적인 방법으로 max를 찾도록 하면 맞았습니다가 뜨는데 *max_element를 쓰면 런타임에러가 나는 이유가 뭔지 알수있을까요??
  • 끼루끼루
    안녕하세요! 강의 보는 중에 질문이 하나 있어 댓글 남기게 됐습니다.

    강의자료 BFS 29 슬라이드 예시코드에서

    if(nx < 0 or nx >= n or ny < 0 or ny >= m) continue; // 범위 밖일 경우 넘어감
    if(vis[nx][ny] or board[nx][ny] != 1) continue; // 이미 방문한 칸이거나 파란 칸이 아닐 경우

    이 코드에 대한 간단한 질문인데요.

    || 연산자가 아닌 or을 그대로 썼는데도 돌아가는게 신기해서요

    and or 그대로 써도 돌아가는건 이유가 궁금합니다!
    • https://en.cppreference.com/w/cpp/keyword

      C++ 표준 상으로 or, and, xor 등은 이미 존재하는 keyword입니다.

      GCC에서는 정상적으로 동작하는데 Visual Studio 2017이 표준을 지키지 않아 발생하는 문제입니다.

      해결방안으로는

      1
      #include <ciso646>를 추가한다.

      2
      #define and &&
      #define or ||
      #define xor ^ 를 추가한다.

      3
      그냥 직접 모든 and를 &&로, or를 ||로, xor을 ^로 바꾼다.

      가 있습니다. 다만 실제 코딩테스트 대회장의 환경도 그렇고 다수의 독자 분들이 Visual Studio 2017을 사용함을 감안해 다음에 강의 자료를 수정할 때 직접 and, or를 다 바꾸도록 하겠습니다.
  • 연구맨
    바킹독님 절 가지세요! 당장이요! 사랑해요!
  • jink
    https://daru-daru.tistory.com/40
    이 문제에서 제가 봤을 때 영역은 하나인거 같은데 왜 12개인지 알 수 있을까요?
    점 한군데로부터 계속 탐색하면 분홍색 한 영역만 나올 것 같은데 아닌가요?
  • 코린임돠
    항상 잘보고 있습니다.
    질문이 있어서요. 미로에서 fill(dist[i],dist[i]+m, -1) 이 부분에 대해서 설명좀 부탁드리겠습니다.
    그리고 왜 string 를 쓰셨는지 궁금합니다.
    • dist가 2차원 배열일 때 fill(dist[i], dist[i]+m, -1)은 dist[i][0], dist[i][1], dist[i][2], ... , dist[i][m-1]의 값을 -1로 만드는 연산입니다.

      입력 형식이 1 0 1 0 1 1 .. 이었으면 그냥 int 배열을 썼을텐데 붙어있다보니 map을 입력받기 위해 string을 사용했습니다. 그냥 char board[102][102]로 두거나 scanf("%1d", &...)을 활용해도 크게 상관이 없습니다만 scanf를 쓸 경우 cin과 혼용하지 않도록 해야합니다.
  • 알린이
    dfs를 재귀로 구현하는 경우 불이익이 있을까요?
  • To do : STL queue, stack의 경우 생성자를 호출할 때 시간이 오래 걸려 로직 상애서 STL queue or stack을 많이 생성할 경우 예상치못하게 시간 초과를 받을 수 있음을 명시(1000만번에 대략 1.268s, https://www.acmicpc.net/source/share/209788a95adf47309dd394acf4fdf414)
댓글 쓰기