[실전 알고리즘] 0x09강 - BFS

안녕하세요 여러분, 드디어 올 것이 왔습니다. 마음의 준비를 단단히 하셔야 합니다.. 드디어 실전 알고리즘 강의에서 첫 번째 고비에 도달했는데 이 강의와 함께 이번 고비를 잘 헤쳐나가면 좋겠습니다.

 

0x05까지 있으니 목차를 보시면 뭐가 되게 많죠? 사실 리뉴얼 하기 전의 강의에서는 기본적인 BFS만 다뤘는데 늘 내용을 보충하고 싶었습니다. 그래서 리뉴얼한 강의에서는 BFS의 다양한 응용 내지는 유형들을 전부 짚고 넘어갈 것입니다.

 

BFS를 알아보기 전에 우리에게 익숙한 문제를 가지고 얘기를 시작해보겠습니다. 대충 물고기 사진을 하나 가져왔는데, 그림판의 페인트 기능을 이용하면 물고기의 색을 바꿀 수가 있습니다. 페인트 기능은 외부 윤곽선을 따라서 구분되는 영역의 색을 한꺼번에 바꾸는 거고, 이런걸 Flood Fill이라고 부르기도 합니다.

 

그런데 이 Flood Fill 기능은 어떻게 구현할 수 있을까요? 일단 클릭한 칸의 상하좌우를 보여 나와 색이 같은지 확인하고, 같은 칸에 대해서 또 상하좌우로 확인하고… 뭔가 좀 막연합니다. 지금까지 배운 지식으로는 이 기능을 구현하는 게 쉽지 않지만, 이번에 배울 BFS라는 알고리즘을 가지고 해결할 수 있게 됩니다.

 

그래서 계속 BFS BFS하는데 도대체 그게 뭔가 하면, 여기 적힌 대로 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘입니다. 그런데 BFS라는 단어가 굉장히 낯설 텐데 저 표현을 보고 나면 저 혼란스러울 것 같습니다. 대체 너비를 우선으로 방문한다는 게 뭔 소리지… 싶을텐데, 달리 어떻게 설명할 방법이 없습니다.

 

왜냐하면 원래 BFS는 그래프라는 자료구조에서 모든 노드를 방문하기 위한 알고리즘입니다. 여기서 말하는 그래프는 우리가 흔히 아는 왼쪽과 같은 형태의 그래프가 아니라 오른쪽 모양의 그래프이고, 정확한 정의는 정점과 간선으로 이루어진 자료구조입니다.

 

그렇기 때문에 BFS를 정확하게 이해하려면 그래프 자료구조에 대한 이해가 선행되어야 하는데 그건 배보다 배꼽이 더 큰 느낌입니다. 그래서 BFS를 엄밀하게 정의할 수는 없지만, 실제로 어떻게 동작하는지를 보면서 다차원 배열에서의 BFS를 이해해보도록 하겠습니다.

 

이전 강의 자료에서는 마치 설명서처럼 일단 방법을 글로 먼저 설명해두었는데 생소한 내용이다 보니 설명을 봐도 전혀 감이 안 올 것 같습니다. 그래서 그냥 실제 BFS를 돌리는걸 한 번 보고 가겠습니다. 저희의 목표는 (0, 0)과 상하좌우로 이어진 모든 파란색 칸을 확인하는 것입니다. 이 문제를 BFS로 어떻게 해결하는지 보겠습니다.

 

우선 BFS 알고리즘에서는 좌표를 담을 큐가 필요합니다. BFS 알고리즘이 시작되면 우선 (0, 0)에 방문했다는 표시를 남기고 해당 칸을 큐에 넣습니다. 이 초기 세팅이 끝난 후에는 큐가 빌 때까지 계속 큐의 front를 빼고 해당 좌표의 상하좌우를 살펴보면서 큐에 넣어주는 작업을 반복하게 됩니다.

 

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

 

지금 상황을 보면 (0, 0)과 상하좌우로 인접한 (0, 1)과 (1, 0)은 모두 파란 칸이면서 아직 방문하지 않았습니다. 이 2개의 칸에 방문했다는 표시를 남기고 큐에 넣습니다.

 

(0, 0)에서 할건 다 했고, 다음으로 넘어갑니다. 현재 큐의 front는 (0, 1)이고 pop을 합니다. 참고로 (0, 1)에서 0은 행을 의미하고 1은 열을 의미합니다. 그리고 이번에도 (0, 1)의 상하좌우 칸을 확인합니다. 이 칸들 중에서 (0, 0)은 파란 칸이지만 이미 방문을 했고, (1, 1)은 빨간 칸입니다. 유일하게 (0, 2)만 파란색 칸이면서 아직 방문하지 않은 칸이니까 (0, 2)에 방문했다는 표시를 남기고 큐에 넣습니다.

 

계속 이런식으로 큐의 front를 pop하고 인접한 칸 중에서 방문하지 않은 파란색 칸에 표시를 남기고 큐에 넣어주면 되는데, 이후로는 한 번에 쭉 보여드릴 테니 아래의 예시를 확인해봅시다.

 

이렇게 큐가 빈 순간 과정은 종료되고 (0, 0)과 상하좌우로 이어진 모든 파란 칸을 잘 방문했음을 알 수 있습니다.

 

이렇게 BFS 과정을 같이 살펴봤는데 이해가 잘 가실지 모르겠습니다. 이제 과정을 step by step으로 설명드리겠습니다. 일단 시작하는 칸을 큐에 넣고 방문했다는 표시를 남깁니다. 그리고 큐가 빌 때까지 큐에서 원소를 꺼내고 상하좌우로 인접한 칸에 대해 처음으로 방문했다면 해당 칸을 큐에 삽입하는 것을 반복하면 됩니다.

 

BFS의 시간복잡도를 생각해보면 방문 표시를 남기기 때문에 모든 칸은 큐에 1번씩만 들어가게 됩니다. 그렇기 때문에 시간복잡도는 칸이 N개일 때 O(N)이 됩니다. 만약 행이 R개이고 열이 C개이면 O(RC)가 될 것입니다.

 

BFS의 구현을 다루기 전에 코드에서 쓰이게 될 STL을 하나 소개해드리겠습니다. 바로 utility 헤더에 있는 pair인데, pair를 이용하면 두 자료형을 묶어서 가지고 다닐 수 있습니다. make_pair로 값을 넣어줄 수도 있고, C++11 이상에서는 그냥 중괄호를 써서 쉽게 해결할 수 있습니다.

 

값의 접근은 각각 first, second를 부름으로서 가능하고 또 pair에는 미리 대소 관계가 설정되어 있어서 편합니다. 알아서 앞쪽의 값을 먼저 비교하고, 이후 뒤쪽의 값을 비교합니다.

 

BFS를 구현할 때 큐에 좌표를 넣어야 하는데, 이때 pair를 쓸 것입니다. (레퍼런스 링크, 예제 링크)

 

이제 BFS를 코드로 어떻게 짜면 될지 고민해보겠습니다. 앞에서 본 것과 같이 큐에서 원소를 빼고 상하좌우의 칸을 확인하는 식으로 구현하면 되는데, 아마 직접 짜 보려고한다면 아마 굉장히 비효율적으로 짜게 될 것입니다. 직접 시도해보는 것도 정말 좋은 자세이지만 BFS는 어느 정도 정석적인 구현이 있어서 지금 보여드릴 코드를 거의 외우다시피 해도 괜찮습니다. 특히 삼성 A형을 치기 위해서는 BFS가 정말 숙달되어 있어야 하는데, 어느 정도냐면 자고 있다가 누가 툭 쳐서 BFS를 짜라고 시켜도 한 5분 내로 기본 틀을 좌르륵 쳐낼 수 있어야 합니다.

 

일단 코드를 보겠습니다. 공간이 좁아서 주석을 많이 뺐는데, 저기 깃헙 링크에 들어가서 정확하게 코드를 확인해보는 걸 추천드립니다. 아무튼 코드가 굉장히 낯설 텐데 같이 이해를 해보겠습니다.

 

일단 03, 04번째 줄에서 #define을 해놓은 건 pair를 조금 더 편하게 쓰기 쓰기 위함인데, first/second 대신 t.X/t.Y로 쓰고 싶어서 저렇게 했습니다.

 

그다음 쭉 있는 변수들의 역할이 궁금할 텐데 하나씩 설명을 드리겠습니다. board는 말 그대로 판을 의미합니다. 1이면 파란 칸이고 0이면 빨간 칸이라고 생각하면 됩니다. 그리고 vis는 방문 여부를 저장할 변수입니다. 칸 위에 올리던 동그라미를 코드 상에서는 vis 값을 1로 변경함으로써 처리하는 것입니다. 그리고 n과 m은 각각 행과 열의 개수를 의미하고, dx와 dy는 상하좌우를 영리하게 처리하기 위한 변수인데 이건 실제로 쓰일 때 설명을 드리겠습니다.

 

그 후로 (0, 0)에 방문 표시를 하고 큐에 추가하는 과정이 코드에서는 14, 15번 줄이 됐습니다. 그다음에는 큐가 빌 때까지그 상하좌우의 칸을 추가하는걸 쭉 반복하는데, 일단 큐의 front를 cur에 저장하고 pop을 합니다. 그다음 줄은 그냥 방문 순서를 나타내 주기 위해서 넣은 출력문입니다.

 

19번째 줄에서 26번째 줄까지의 루틴이 좀 중요한 루틴입니다. 아까 정체를 알 수 없던 dx, dy가 여기서 쓰입니다. 판에서 저희가 상하좌우를 생각해보면 오른쪽 아래의 그림과 같습니다. 그런데 노파심에 말을 하자면, 이 코드에서 x가 행을, y가 열을 의미합니다. 그런데 사람에 따라 x가 열이고 y가 행인 게 더 익숙할 수 있습니다. 이게 별게 아닐 수 있지만 생각을 할 때 굉장히 헷갈리게 하는 요소가 될 수 있습니다. 당장 지금 저 그림도 만약 x가 열이고 y가 행이라면 왼쪽 칸이 x-1, y가 되어야 합니다. 뭐 어떻게 하든 답은 잘 나오겠지만 저 뿐만 아니라 대부분의 BFS 코드에서 x가 행을, y가 열을 의미하는 경우가 많았어서 이 방식으로 따라오시는게 좋을 것 같습니다.

 

아무튼 우리는 (cur.X, cur.Y)에 대해 상하좌우 칸인 (cur.X-1, cur.Y), (cur.X, cur.Y-1), (cur.X, cur.Y+1), (cur.X+1, cur.Y)를 확인할 필요가 있습니다. 그리고 이걸 쉽게 하는 방법이 바로 19번째 줄부터 이어지는 for문인데, nx와 ny의 값을 같이 봅시다. 보면 cur.X, cur.Y에 dx[dir], dy[dir]을 각각 더하죠? 그리고 08, 09번째 줄로 시선을 돌려보면 dx[dir], dy[dir] 값이 (1, 0), (0, 1), (-1, 0), (0, -1)이니까 nx, ny에 상하좌우의 좌표값이 깔끔하게 담긴다는 것을 알 수 있습니다. dx, dy 값에 따른 순서는 아랫쪽, 오른쪽, 윗쪽, 왼쪽 순서이긴 한데 이건 크게 중요하지는 않습니다.

 

이후 22번째 줄에서 일단 범위에 들어오는지를 확인하고, 23번째 줄에서 이미 방문했거나 파란 칸이 아닌 경우를 걸러내고 난 후에는 방문했다는 표시를 vis[nx][ny] = 1로 바꿈으로서 남기고 큐에 추가해주면 됩니다. 만약 22번째 줄과 23번째 줄의 순서가 바뀌면 어떻게 될까요? 그렇게 되면 vis[-1][0]과 같은 값을 참조할 수 있어서 런타임에러가 날 수 있습니다. 그렇기 떄문에 일단 범위 내에 들어오는지를 꼭 먼저 확인한 후에 vis, board 배열값을 봐야합니다.

 

제 코드를 보기 전에 BFS를 먼저 구현해보려고 시도해보셨다면 아마 높은 확률로 뭔가 비효율적이거나 잘못 동작하는 코드를 짰을 것입니다. 조금만 익숙해지면 그냥 정석적인 구현을 거의 복붙하다시피 할 수 있겠지만 그래도 구현을 시도해보실 분들을 위해 자주 실수하는 점들을 몇 개 짚고 가겠습니다.

 

첫 번째로, 시작점을 큐에 넣긴하는데 정작 방문했다는 표시를 남기지 않은 채로 진행하는 경우가 있습니다. 이렇게 되면 시작점을 두 번 방문할 수가 있습니다.

 

두 번째는 큐에 넣을 때 해당 칸에 방문했다는 표시를 남기지 않고 큐에서 빼낼 때 남기는 경우인데, 이렇게 되면 같은 칸이 큐에 여러 번 들어가게 되어서 시간 초과나 메모리 초과가 발생할 수 있습니다. 특히 이건 보통 예제로 주는 작은 케이스에서는 잘 돌아가다가 실제 제출을 했을 때 터지는 경우가 많기 때문에 주의해야 합니다.

 

세 번째는 앞의 코드에서 있던 nx, ny가 배열 바깥으로 벗어났는지에 대한 루틴을 아예 빼먹었거나, 아니면 이상하게 구현을 한 상황을 말합니다.

 

직접 짠 BFS가 좀 이상하면 이런 점들을 체크해볼 수 있겠죠?

 

지금부터 BFS를 이용해서 해결할 수 있는 문제를 살펴보도록 하겠습니다. BOJ 1926그림 문제를 확인해보겠습니다.

 

우리는 지금 하나의 시작점에서 BFS를 도는 방법만 익혔는데 이 문제에서는 주어진 도화지에서 모든 그림을 찾아야하고, 크기도 알아내야 합니다. 꽤 어려운게 아닌가 싶을수도 있는데 지금 이 문제 정도면 BFS의 기본 예제 정도라고 생각하시면 됩니다. 쉽지는 않겠지만 한 번 고민해보는 시간을 가지도록 하겠습니다. 먼저 도전해보셔도 괜찮습니다.

 

그런데 사실 오늘 처음 BFS를 배웠으면 어려운게 당연한거라, 도움이 될만한 팁을 살짝 드려보겠습니다. 결국 이 문제를 해결하기 위해 우리가 해야할 일은 상하좌우로 연결된 그림의 크기를 알아내기, 도화지에 있는 모든 그림을 찾아내기 이 2개입니다.

 

첫 번째의 경우는 크게 어렵지는 않은게, 그냥 큐에서 pop을 몇 번 하는지만 세면 끝입니다.

 

문제는 두 번째인데, 우리는 지금 어떤 한 시작점과 이어진 그림만 찾아내는 법만 알고 있기 때문에 뭔가 고민을 좀 해볼 필요가 있습니다.

 

지금 나타낸 그림은 주어진 예제인데, 여기 있는 4개의 그림을 어떤 식으로 찾아야할까요? 이 부분은 이중 for문을 돌면서 BFS의 시작점이 될 수 있는 곳을 찾으면 됩니다. 무슨 소린가 싶을텐데 이런 느낌입니다.

 

일단 (0, 0)는 파란 칸이고 아직 방문을 안했으니 여기서 BFS를 시작하면 크기가 4인 그림이 찾아질 것입니다. BFS를 돌고 나면 방문 표시도 적절하게 남게 됩니다.

 

그리고 그 후로 (0, 1)이 시작점이 될 수 있는지보면 (0, 1)은 파란 칸이지만 이미 방문을 했으니 여기서 또 BFS를 돌리면 안되겠죠.

 

다음에는 (0, 2)인데 여기는 애초에 빨간 칸이니 거릅니다.

 

그 다음 (0, 3)은 파란 칸이고 아직 방문을 하지 않았으니 새로운 그림입니다. 그렇기 때문에 여기서 BFS를 시작합니다.

 

이와 같이 이중 for문으로 각 칸이 BFS의 시작점이 될 수 있는지를 체크해주면 도화지에 있는 모든 그림을 찾아낼 수 있습니다. 그리고 여기서도 결국 각 파란 칸은 큐에 딱 한 번씩만 들어가서 시간복잡도는 칸의 갯수만큼만 필요합니다. 이 문제에서는 O(nm)입니다.

 

방법은 알았으니 구현을 하면 됩니다. 제 코드를 한 번 감상해보시면 앞의 BFS 코드에서 조금만 변형한걸 알 수 있습니다. 천천히 코드를 분석해보면 말한대로 이중 for문을 돌면서 (i, j)가 BFS의 시작점이 될 수 있는지 확인합니다. 빨간 칸이거나 이미 방문했으면 제외하고, 이후 그 점을 시작점으로 BFS를 돌립니다.

 

그리고 while문 안에서 pop이 이루어질 때 마다 area값을 1 증가시키면 area의 값이 곧 그림의 넓이가 됩니다. BFS의 과정을 잘 이해하고 있다면 이 정도의 응용은 따라가는데 큰 무리가 없을 것 같은데, 아직 조금 아리까리하다면 과정을 계속 들여다보면서 확실하게 이해할 필요가 있어보입니다. (코드 링크)

 

BFS로 Flood Fill을 수행하는 것을 같이 살펴봤는데, Flood Fill 말고도 정말 다양한 응용이 있고, 안타깝게도 BFS는 코딩테스트 단골 문제이기 때문에 이런 응용들을 모두 잘 알고 있어야합니다. 그 응용 중에서 첫 번째로 다차원 배열에서의 거리 측정을 보겠습니다. BOJ 2178번 미로 탐색 문제를 확인해봅시다.

 

문제를 보시면 이 문제는 미로의 좌측 상단으로부터 우측 하단으로 가는 최단 경로의 길이를 찾는 문제입니다. 그리고 BFS를 이용해 시작점에서 연결된 다른 모든 점으로의 최단 경로를 찾을 수 있습니다.

 

이 성질을 이해하기 위해 BFS의 과정을 다시 살펴보겠습니다. 지금 상황은 (0, 0)에서 BFS를 도는 상황인데, 뭔가 (0, 0)에서 사방으로 퍼져나가는 것과 같은 느낌이 들지 않나요? 감이 잘 안온다면 다음 슬라이드를 같이 보겠습니다.

 

이번에는 방문했다는 표시 대신에 각 칸들에 (0, 0)까지의 거리를 적어놨는데 눈에 들어오는게 있나요? 보면 빨간색 칸은 현재 보는 칸이고 검정색은 추가되는 칸인데, 현재 보고 있는 칸으로부터 추가되는 인접한 칸은 거리가 현재 보는 칸보다 1만큼 더 떨어져 있습니다.

 

제일 첫 번째는 빨간색 칸에서 거리가 0인데 검정색 칸에서 거리가 1이고, 마지막껀 빨간색 칸에서 거리가 4인데 검정색 칸에서는 거리가 5입니다. 이 성질을 활용하면 우리는 단순히 상하좌우로 연결된 칸들을 방문하는 것에서 끝나는 것이 아니라, 시작점과의 거리를 전부 계산할 수 있습니다.

 

구현의 흐름은 일반적인 BFS와 크게 다르지 않습니다. 거리를 저장할 dist 배열을 두고 상하좌우의 칸을 볼 때 값을 잘 넣어주면 됩니다. 그리고 이 배열을 미리 -1로 초기화해두면 굳이 vis 배열을 따로 두지 않아도 방문 여부를 확인할 수 있게 됩니다.

 

구현한 코드를 같이 봅시다. 일단 입력을 string 배열에 받았고 dist 배열은 전부 -1로 초기화시켜뒀습니다. 초기화를 할 때 fill을 썼는데 잘 이해가 안가면 0x03강을 참고하셔도 좋고, 그냥 fill 대신 이중 for문을 돌면서 -1을 대입해도 아무 상관 없습니다. 그리고 큐 안에서 도는 과정은 vis 대신 dist를 썼다는 것만 차이가 있고 크게 달라진게 없어서 이해에 큰 무리가 없을 것 같습니다.

 

BFS로 거리를 잴 수 있는 것도 알았으니 다음 응용으로 넘어가겠습니다. BOJ 7576번 토마토 문제를 확인하고 옵시다. 일단 이 문제가 BFS라는걸 보고 캐치하실 수 있으셨는지 궁금합니다. 토마토가 익어가는 상황 자체가 BFS를 하는 것과 똑같기도 하고, 토마토가 다 익기까지 필요한 최소 일수를 구하려면 모든 익지 않은 토마토들에 대해 가장 가깝게 위치한 익은 토마토까지의 거리를 구해야한다는 관점에서 살펴봐도 마찬가지로 BFS를 활용할 수 있겠다는 생각이 들 것입니다.

 

그래서 만약 익은 토마토가 1개였다면 앞의 미로 탐색 문제랑 비슷하게 익은 토마토가 있는 곳을 시작점으로 해서 BFS를 돌려 쉽게 해결이 가능할텐데 이 문제에서는 익은 토마토의 갯수가 여러 개일 수 있습니다. 각 익은 토마토들에 대해 해당 위치를 시작점으로 하는 BFS를 한 번씩 다 돌리는 방법을 떠올릴 수 있지만, 그러면 BFS의 시간복잡도가 O(NM)이고 익은 토마토 또한 최대 NM개가 있을 수 있으니 총 O(N2M2)이 되어 시간 내로 해결이 안될 것입니다. 과연 어떻게 문제를 해결할 수 있을까요?

 

지금까지의 상황을 다시 정리해보면 우리는 지금 시작점이 여러 개인 BFS를 돌 수 있어야합니다. 그리고 해결법은 의외로 간단한데, 그냥 모든 시작점을 큐에 넣고 앞에서 한 것과 똑같이 BFS를 돌면 끝입니다. 지금 슬라이드에서의 그림을 보면 파란색은 익지 않은 토마토, 초록색은 익은 토마토, 빨간색은 빈 칸을 의미합니다. 현재 익은 토마토가 2개가 있는데, 그 2개를 큐에 넣어두고 BFS를 돌리면 이렇게 자연스럽게 거리가 잘 구해지게 됩니다.

 

코드를 한 번 보겠습니다. 일단 입력을 받으면서 익은 토마토는 큐에 넣고, 익지 않은 토마토는 dist 값을 -1로 둡니다. 노파심에 말을 드리는데 전역 변수로 잡은 int나 int 배열은 따로 초기화를 안하면 0이 채워지니 익은 토마토가 들어있거나 빈 칸인 곳은 dist 값이 0인 것을 인지하고 코드를 확인하셔야 합니다.

 

이후 BFS를 도는 부분은 크게 특이한 점이 없고, 마지막에 답을 출력할 땐 거리가 가장 먼 것을 찾지만 익지 않은 토마토가 있는지를 꼭 확인해줘야 합니다. 이렇게 토마토 문제를 처리할 수 있습니다. 참고로 BOJ 7569번: 토마토 문제는 거의 똑같은데 3차원입니다.

 

3차원이라고 해서 크게 다를건 없고, 단지 배열이 3차원이고 6개의 인접한 칸을 처리하기 위해 dx, dy, dz가 필요하게 됩니다. 이 문제는 여러분에게 맡기겠습니다. 구현할 때 STL tuple이라고 하는 것을 이용하면 좋습니다.

 

그리고 이 문제를 풀 때에는 쓰이지 않았지만 알아둘 필요가 있는 BFS의 성질이 하나 더 있는데, 앞의 코드가 어떤 식으로 동작하는지 같이 생각해보겠습니다.

 

문제에서의 표현은 익은 토마토와 익지 않은 토마토이긴 한데, 그냥 여러 개의 시작점에서 모든 지점으로의 거리를 구하는 문제라는 것을 우리는 알고 있습니다.

 

코드를 다시 떠올려보면 일단 익은 토마토, 즉 거리가 0인 칸들을 큐에 다 넣습니다.

 

이 때 첫 번째 칸을 통해 추가되는 칸은 앞에서 같이 본 성질로 인해 거리가 1입니다. 

 

그 다음 칸을 통해 추가되는 칸들도 마찬가지로 거리가 1입니다. 

 

이제 거리가 0인 칸들은 큐에서 다 빠졌고, 순차적으로 1인 칸들을 pop할텐데 잘 생각해보면 1인 칸들을 pop하는 동안 거리가 2인 칸들이 쭉 추가될 것입니다.

 

거리가 1인 칸들이 다 빠지고 2인 칸들을 볼 때면 3인 칸들이 쭉 추가될 것입니다. 이제 전체적인 큐의 모양을 확인해보시면 이와 같이 BFS를 돌 때 큐에 쌓이는 순서는 반드시 거리 순이게 됩니다.

 

이제 응용 4개 중에 절반을 끝냈습니다. 마저 화이팅합시다. BOJ 4179번 불! 문제를 확인합시다. 확인해보면 아마 굉장히 막막할 것 같은데 그래도 BFS 파트에 소개했다는건 BFS로 풀 수 있다는 얘기일테니, 한 번 고민을 해봅시다.

 

지금까지 배운 내용을 잘 이해했다면 불의 전파를 BFS로 처리할 수 있음을 알 수 있을 것입니다. 그런데 지금은 지훈이의 탈출도 같이 처리를 해주어야 하고, 이게 꽤 어렵습니다. 일단 결론적으로 말해 이런 문제는 불에 대한 BFS와 지훈이에 대한 BFS를 모두 돌림으로서 해결이 가능합니다.

 

먼저 지훈이는 신경쓰지 말고 불에 대한 BFS를 돌려서 미리 각 칸에 불이 전파되는 시간을 다 구해둡니다. 두 번째의 맵이  바로 각 칸에 불이 전파시간을 의미합니다.

 

그 다음에는 지훈이에 대한 BFS를 돌리며 지훈이를 이동시킵니다. 이 때 만약 지훈이가 특정 칸을 x시간에 최초로 방문할 수 있는데 그 칸에는 x시간이나 그 이전에 불이 붙는다면 그 칸을 못가게 됩니다.

 

예를 들어 **으로 마킹한 칸을 보면 지훈이는 저 칸에 2시간이 될 때 방문하게 됩니다. 그런데 불은 이미 1시간만에 전파되었기 때문에 지훈이는 저 곳을 갈 수 없습니다. *, ***으로 마킹한 칸도 마찬가지 이유로 지훈이가 갈 수 없는 칸입니다.

 

원래 BFS의 구현에서는 큐 안에서 (nx, ny)를 살펴볼때 방문했는지 여부를 vis[nx][ny]가 true인지 혹은 dist[nx][ny]가 0 이상인지 확인하고, 이미 방문한 칸이라면 continue를 합니다. 이 문제에서는 추가로 해당 칸에 불이 붙은 시간을 확인해서 필요에 따라 continue를 하면 됩니다. 이렇게 BFS와 지훈이에 대한 BFS를 따로 해서 문제를 그렇게 어렵지는 않게 해결할 수 있습니다.

 

지금 이 방식을 토대로 구현해보는 시간을 가져보도록 하겠습니다. 한 번 시도해봅시다.

 

지금까지 같이 배운 것을 토대로 구현을 하면 어렵긴 해도 못할 난이도는 아닐 것 같은데 어떤지 모르겠습니다. 일단 제 코드를 같이 보겠습니다.

 

이 문제의 코드는 도저히 한 슬라이드에 다 담을 수가 없었습니다. 한 20줄 정도가 더 남아있는데 일단 지금 여기까지를 한 번 보겠습니다. 불에 대한 BFS는 Q1, dist1을 활용하고 지훈이에 대한 BFS는 Q2, dist2를 활용할 것입니다. 불에 대한 BFS는 늘 해오던 것과 똑같습니다.

 

불에 대한 BFS가 끝나고 나면 dist1에는 해당 지점에 불이 언제 붙는지가 저장됩니다. 그 다음으로는 지훈이에 대한 BFS를 돌면서 외곽으로 빠져나올 수 있게 해야하는데 지금까지의 BFS에서는 목적지가 정해져있거나 더 이상 갈 곳이 없을 때 까지 계속 돌리는 상황이었던 반면 이번에는 외곽으로 탈출을 해야하니 52번째 줄의 처리가 들어가게 됩니다. 주석으로 적어놓은 것 처럼 (nx, ny)가 범위를 벗어났다는건 곧 탈출에 성공했다는 의미이고, 17번 슬라이드에서 본 것과 같이 큐에 원소들은 거리 순으로 들어가니 최초로 탈출한 시간을 바로 출력하고 종료하면 됩니다.

 

그리고 지훈이는 자신이 도착한 시간과 동시에 불이 도착하거나, 혹은 자신보다 더 빨리 불이 도착하는 자리로는 갈 수 없기 때문에 58번째 줄의 조건이 추가로 들어가게 됩니다. 만약 프로그램이 종료되지 않고 while문이 끝나게 된다면 지훈이가 탈출에 실패했다는 의미이니 IMPOSSIBLE을 출력하면 됩니다.

 

이렇게 시작점이 두 종류인 문제를 해결할 수 있게 됩니다. 그런데 시작점이 두 종류인 문제에 관해서 저희가 생각해야 할 점이 사실 추가로 있습니다. 지금 이 방식이 가지고 있는 문제는 무엇인가 하면, 지금은 지훈이의 이동은 불의 전파에 영향을 받지만 불의 전파는 지훈이의 이동에 영향을 받지 않아서 불만 먼저 전파를 쭉 시키는게 가능했습니다. 그런데 예를 들어 시작점이 A, B 두 종류가 있고, A의 전파에 B가 영향을 주고 B의 전파에도 A가 영향을 준다고 해봅시다. 지금 이 문제에서 불과 지훈이가 아니라 불과 소방수 내지는 불과 물이 전파되는 문제여서 둘이 만나면 뭔가 상호작용이 발생한다고 생각을 하는거죠.

 

그런 상황을 생각해보면 어느 하나를 먼저 끝까지 전파시키는게 불가능합니다. 제가 출제했던 18809번 문제가 딱 그런 문제입니다. 아쉽게도 이 문제는 백트래킹 기법을 추가로 알고 있어야 해결이 가능하기 때문에 당장 풀어볼 수는 없지만, 두 종류의 BFS에서 BFS를 돌 때 어느 하나가 독립적이지 않고 서로에게 영향을 준다면 지금 보여드린 방법으로는 해결할 수 없다는 것을 꼭 이해하셔야 합니다. 그런 상황에서는 시간 순으로 A와 B를 동시에 진행시켜야 합니다.

 

이 부분은 충분히 생각해볼 가치가 있고, 두 종류의 시작점 문제를 몇 개 풀다보면 지금 제가 한 얘기가 더 명확하게 이해가 갈 것입니다. 그 때 다른 사람의 코드를 찾아보거나 직접 고민하면서 시간 순으로 A와 B를 동시에 진행시킨다는 의미를 이해해보면 좋겠습니다.

 

드디어 마지막 BFS입니다. 정말 감개무량합니다. BOJ 1697번 숨바꼭질 문제를 한 번 보고 오시면 지금까지 다뤘던 문제들이랑은 느낌이 많이 다른 것을 확인할 수 있습니다. 지금까지는 죄다 2차원 배열 형태에서 상하좌우로 움직이는 모양새였는데 얘는 전혀 다릅니다. 그래서 이게 BFS랑 관계가 있긴 한건가 싶을텐데, 이 문제도 BFS입니다.

 

이차원에서의 BFS를 생각하면 지금 이 그림처럼 현재 선택된 칸에서 상하좌우로 뻗어나가는 방식으로 진행이 됐습니다. 왜 상하좌우로 뻗어갔나 생각해보면 그게 불이 됐든 토마토가 됐든 전파가 상하좌우로 이루어졌기 때문입니다.

 

그럼 약간의 창의성을 발휘해서 아래와 같이 이 문제에서도 수빈이가 X에 있다고 할 때 X-1, X+1, 2X로 이동하는 것을 BFS로 처리할 수 있겠다는 생각을 해볼 수 있습니다.

 

수빈이가 예제처럼 5에 있었다고 치면 5에서 BFS를 시작하고, 5에서 갈 수 있는 4, 6, 10은 거리가 1이 되는 것입니다.

 

BFS는 이제 충분히 익숙해지셨을 것 같아서 큐는 안그려놨는데, 아무튼 그 다음으로는 4가 선택되고 3, 5, 8을 보는데 5는 이미 값이 써져있으니 3, 8만 거리가 2가 될 것입니다. 이렇게 BFS를 돌다가 동생이 있는 위치의 값이 써지게 되면 문제에서 원하는 답을 알 수 있게 됩니다. 구현이 그렇게 어렵지는 않을 것 같은데 어떤가요? 앞의 문제보다 더 쉬울 것 같습니다.

 

그런데 사실 한 가지 더 고민해야 할 문제가 있는데, BFS의 범위를 어디까지로 해야할까요? 0부터 100,000으로 하면 되는거 아닌가하고 쉽게 생각을 하셨을수도 있는데, 문제를 보시면 수빈이와 동생의 위치가 0에서 100,000 사이라고 했지 수빈이가 이동 중에 반드시 0에서 100,000 사이에만 있어야한다는 조건은 없습니다. 예를 들어 100,000 밖으로 나갔다가 다시 안으로 올 수도 있습니다. 그래서 이 부분을 고려할 필요가 있습니다.

 

일단 상식적으로 생각했을 때 음수로 갈 일은 없을 것입니다. 그건 진짜 절대 가장 빠른 경로가 될 수 없기 때문입니다. 그리고 100,000 바깥으로 나갈 수 있겠지만 일단 한 번 나갔다면 그 이후로는 -1만 계속 하게 됩니다. 그렇기 때문에 동생을 가장 빠르게 찾아나가는 상황에서는 아무리 멀리가도 200,000을 넘어가지는 않습니다.

 

이러한 생각을 거쳐서 0에서 200,000 사이에서만 BFS를 돌려도 답을 구하는데는 문제가 없음을 알 수 있게 되고, 여기서 더 깊게 생각을 해보면 사실 100,000을 나가는 것 자체가 손해라는 것을 알 수 있습니다. +1로 100,000을 탈출하는건 정말 바보짓이고, x2로 100,000을 탈출하는 상황이 있을 수 있겠다 싶지만, x2를 한 후 -1을 여러번 할 바에야 -1을 먼저 하고 x2를 하는게 더 낫기 때문입니다.

 

지금 설명이 잘 이해가 가지 않을 수 있습니다. 이해가 가지 않더라도 상관은 없지만 이 문제에서 당연히 수빈이가 0에서 100,000 사이에서만 움직인다고 멋대로 가정을 하고 풀면 안된다는 점은 꼭 짚고 넘어가면 좋겠습니다. 이 문제에서는 운 좋게 논리적으로 생각을 했을 때 수빈이가 0에서 100,000 사이에서만 움직이게 되었지만 다른 문제에서는 멋대로 가정한 것 때문에 말아먹을수도 있습니다.

 

구현에서 크게 어려울건 없을 것 같습니다. 17번째 줄에서 range-based for를 이용했고, 구현 흐름은 늘 보던 것들의 반복입니다. (코드)

 

굉장히 빡센 BFS가 마무리됐습니다. Flood Fill로 시작해서 거리 측정, 시작점이 여러 개일 때, 시작점이 두 종류일 때, 1차원에서의 BFS를 모두 다뤘는데, 한 강의에서 다루기에 정말 많은 분량이긴 했습니다. 하지만 이왕 하는거 여러 응용들을 잘 섭렵하시라고 이렇게 준비를 했고, BFS부터는 본격적으로 코딩테스트에 정말 잘 나오는 유형이기 때문에 그룹 내의 문제집을 꼼꼼하게 풀어보고 BFS의 기본 틀 자체도 반복적으로 짜면서 코드의 흐름을 손에 익힐 필요가 있습니다.

 

그럼 고생 많으셨습니다.

  Comments
  • 이전 댓글 더보기
  • captain teemo
    안녕하세요 바킹독님!
    https://www.acmicpc.net/problem/1600
    문제를 풀다가 이해가 안되는 것이 있어서 질문 드립니다.
    1
    5 5
    0 0 0 0 0
    0 0 0 0 0
    0 0 0 0 0
    0 0 0 1 1
    0 0 0 1 0
    인 테스트 케이스를 돌려보면 배열 결과가
    5 4 3 4 5
    4 3 2 3 4
    3 2 3 4 5
    4 3 4 0 0
    5 4 5 0 7
    이 나오는데, bfs의 특징처럼 동심원으로 거리순서대로 퍼져나간 것이 맞는데
    저기 마지막에 7이 어떻게 들어간 것인지 궁금합니다.. 5의 저장된 위치에서 다 살펴봐도 범위 제한으로 빠지고, 이미 방문해서 빠지고.. 7은 어떻게 들어간 것인가요..? ㅠㅠ
    #include <bits/stdc++.h>
    using namespace std;
    typedef long long ll; //-2^63 ~ 2^63-1
    typedef unsigned long long llu;
    typedef pair<int, int> pii;
    typedef pair<double, double> pdd;
    typedef pair<int, pii> piii;
    typedef pair<ll, ll> pll;
    typedef pair<ll, int> pli;
    typedef pair<int, ll> pil;
    typedef pair<string, int> psi;
    typedef pair<int, char> pic;
    //512MB = 1.2억개 int
    //if(nx<0||nx>=n||ny<0||ny>=m) continue;
    /*int dz[6]={1,-1,0,0,0,0};
    int dx[6]={0,0,1,-1,0,0};
    int dy[6]={0,0,0,0,1,-1};*/ // 3차원 bfs용
    #define X first
    #define Y second
    int dxk[] = {1,2,2,1,-1,-2,-2,-1};
    int dyk[]= {-2,-1,1,2,2,1,-1,-2};
    int k; // k번만 위와같이 움직일 수 있다
    int dx[4]={1,0,-1,0};
    int dy[4]={0,1,0,-1};
    int w,h; // h가 행의 개수 w가 열의 개수
    int board[202][202];
    int vis[32][202][202];
    queue<pair<pair<int,int>,int>> q;
    int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> k; //말처럼 이동할 수 있는 횟수
    //k는 0 이상 30이하의 정수
    cin >> w >> h;
    for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
    cin >> board[i][j];
    }
    }
    //맨 왼쪽 위에서 시작해서 맨 오른쪽 아래까지 가야한다.
    q.push({{0,0},0});
    vis[0][0][0]=1;
    while(!q.empty())
    {
    auto cur=q.front();q.pop();
    if(cur.X.X<k) //k번은 8개의 방향으로 이동이 가능하다.
    {
    for(int dir=0;dir<8;dir++){
    int nx=cur.X.Y+dxk[dir];
    int ny=cur.Y+dyk[dir];
    if(nx<0||nx>=h||ny<0||ny>=w) continue;
    if(board[nx][ny])continue; //1은 장애물이 있는 곳
    if(vis[cur.X.X+1][nx][ny])continue;
    vis[cur.X.X+1][nx][ny]=vis[cur.X.X][cur.X.Y][cur.Y]+1;
    q.push({{cur.X.X+1,nx},ny});
    }
    }
    //k번이 아닐 때는, 상하좌우 4개의 방향으로 이동이 가능하다.
    for(int dir=0;dir<4;dir++){
    int nx=cur.X.Y+dx[dir];
    int ny=cur.Y+dy[dir];
    if(nx<0||nx>=h||ny<0||ny>=w) continue;
    if(board[nx][ny])continue; //1은 장애물이 있는 곳
    if(vis[cur.X.X][nx][ny])continue; //이미 방문한 곳
    vis[cur.X.X][nx][ny]=vis[cur.X.X][cur.X.Y][cur.Y]+1;
    q.push({{cur.X.X,nx},ny});

    }

    }

    for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
    cout << vis[1][i][j] << " ";
    }
    cout << '\n';
    }




    /*
    1
    5 5
    0 0 0 0 0
    0 0 0 0 0
    0 0 0 0 0
    0 0 0 1 1
    0 0 0 1 0
    정답 6
    내 답: -1
    */



    return 0;
    }
    코드입니다!!
    • 질문이 잘 이해가 안가긴하는데 일단 vis[1][4][4]가 7인 이유는 vis[0][3][2] = 6에서 말로 한 번 뛰어서 왔기 때문이죠
    • 질문을 이상하게 드려서 죄송합니다. ㅠㅠ
      바킹독님 말씀대로 vis[0][3][2]에서 한번 뛰어서 와서 vis[1][4][4]가 7인것은 이해했는데, 정답 코드를 보면
      while (!Q.empty()) {
      int vk, vx, vy;
      tie(vk, vx, vy) = Q.front();
      Q.pop();
      if (vk < Kn) {
      for (int i = 0; i < 8; i++) {
      int nx = vx + dkx[i], ny = vy + dky[i];
      if (nx < 0 || ny < 0 || bX <= nx || bY <= ny) continue;
      if (board[nx][ny]) continue;
      if (vis[vk + 1][nx][ny]) continue;
      vis[vk + 1][nx][ny] = vis[vk][vx][vy] + 1;
      Q.push({ vk + 1, nx, ny });
      }
      }
      for (int i = 0; i < 4; i++) {
      int nx = vx + dmx[i], ny = vy + dmy[i];
      if (nx < 0 || ny < 0 || bX <= nx || bY <= ny) continue;
      if (board[nx][ny]) continue;
      if (vis[vk][nx][ny]) continue;
      vis[vk][nx][ny] = vis[vk][vx][vy] + 1;
      Q.push({ vk, nx, ny });
      }
      }
      if문이 참이라서 안으로 들어가고 8방향 이동 가능한 말의 모드(?)로 바뀌게 되는데 그러면 말의 모드가 시작점에서만 가능한 것이 아닌지.. 가 제 의문이었습니다 ㅠㅠ 바킹독님 말씀대로 원숭이 모드로 쭉 가다가 마지막에 말 모드를 써야하는데 저 코드라면 말 모드를 처음에 쓴것이 아닌가 싶어.. 질문 드립니다 !!
    • 시작점이 (0,0)이고 //문제 조건

      만약 k(말이 이동할 수 있는 횟수)가 1번이라면 처음에 기 기회를 무조건 써야하는게아닌지.. 싶어서요.. ㅠㅠ 너무 어렵네요..
    • 원숭이 모드로 쭉 가다가 마지막에 말 모드를 써야하는데 --> 아닙니다

      그냥 현재 상태에서 말 모드와 원숭이 모드를 다 써봐야하는거죠.

      만약 k(말이 이동할 수 있는 횟수)가 1번이라면 처음에 기회를 무조건 써야하는게아닌지 --> 이것도 아닙니다.

      예를 들어
      1
      5 5
      0 0 0 0 0
      0 0 0 0 0
      0 0 0 0 0
      0 0 0 1 1
      0 0 0 1 0

      이면 제일 마지막에 원숭이 점프를 뛰어야겠죠. 그냥 현재 상태에서 말 모드와 원숭이 모드를 다 써보는거고, 이 문제의 풀이에서 '상태 공간'이 어떻게 정의되는지, 왜 vis가 3차원인지 잘 고민해보세요.
    • 벽 부수고 이동하기 문제도 그렇고
      상태 공간의 정의가 중요하네요..
      다시한번 살펴보겠습니다!!
      항상 감사합니다!!
    • 댓글 원칙을 지금 봤네요ㅠㅠ 앞으로는 제출 링크를 올리도록 할게요 죄송합니다 ㅠㅠ!!
    • ㅋㅋㅋㅋ 괜찮아요 울지마세요,,,
  • jcreate98
    안녕하세요! BFS 문제를 풀다가 막혀서 질문 남겨봐요!

    https://www.acmicpc.net/board/view/84935

    벽 부수기 1에서는 기회가 1번으로 제한이 있어서 2차원 배열 2개를 이용해서 풀었는데
    여기서는 10번 까지 가능해 2차원 배열 10개를 이어붙힌 3차원 배열을 써봤습니다

    제출 해보니 시간 초과가 나와서 로직을 건들어야 할 것 같은데 제가 놓치고 있는 부분이 어딘지 궁금합니다!
    • 1. fill을 저렇게 쓰는건 undefined behavior여서 ( https://stackoverflow.com/questions/7269099/may-i-treat-a-2d-array-as-a-contiguous-1d-array ) 동작은 잘 하겠지만 비추천합니다. 그냥 전역으로 빼거나 2중 for문으로 하나하나 fill 해줘야해요.

      2. 1번에서 언급한 수정을 했는데도 시간 초과가 여전히 뜹니다. 분석을 도와드리고 싶은데 코드 가독성이 안좋아서 보기가 좀 힘이 듭니다. get<1>(temp) + dx[i] 이런 식으로 계속 쓰지 말고 제가 자주 쓰던 코드들 참고해서 nx, ny, nz(혹은 nk) 이런 식으로 변수들을 선언해주세요. 현재값도 get<0>(temp)로 계속 가져오지 말고 curx, cury 같은 변수에 둬주세요. x, y 방향도 강의에서 쓰는 방향으로 코드를 수정하고 다시 댓글 달아주세요.
    • 댓글은 봤는데 개강하느라 너무 늦게 올렸네요

      https://www.acmicpc.net/source/39897855

      일단 queue 계산하는 부분을 일단 수정 해봤습니다

      수정하다 보니 벽 부술 때마다 한단계 씩 내려가고 내려가다보면 나선으로 타고 내려가는 등 ([9][0][0] -> [8][1][0] -> [7][1][1] -> [6][0][1] -> [5][0][0]) 필요없는 계산이 늘어나는 것 같은데 이런 것들을 피할만한 방법이 혹시 있을까요..?
    • https://www.acmicpc.net/source/39897855

      헐 공개설정이 안되어 있었네요.. 죄송해요
    • 훨씬 보기 편하네요ㅎㅎ,,, 67번째줄 잘 살펴보세요. 저거 수정해서 통과됐어요. 그리고 fill 관련해서 위에 써놓은것도 다시 확인해보세요.
    • 헉.. 이런 부분을 실수 했었네요.. 보자마자 뭐 잘못 쳤는지 알았습니다..

      fill 부분 고친 줄 알았었는데 안고쳤었네요.. 분명 roof 문으로 바꿨던 것 같은데 ㅠㅠ

      문제 풀기 전에 한번 씩 코드 가시성 좋게 바꾸는 연습부터 시작해야겠어요..

      감사합니다!
  • 안녕하세요! 토마토 문제 관련하여 질문드립니다. 다른 분께서 질문해주셨는데 그걸 봐도 제대로 이해하지 못했습니다.

    이전에 그림 문제에서는 시작점을 for문으로 돌면서 전부 탐색하고 토마토 문제에서는 시작하는 점을 큐에 넣고 시작했는데 이 차이가 궁금합니다. 그림 문제는 1끼리 가까울 거라는, 토마토는 1끼리 멀 거라는 예상에 이렇게 시작하는 건가요?

    바킹독님 게시글 하나씩 다 읽어보고 하트 누르고 있습니다. 정말 감사합니다!
    • 이전에 댓글 달았던 것과 마찬가지로 그림 문제에서는 flood fill을 수행해야 하고 토마토 문제에서는 익지 않은 토마토와의 거리를 재야합니다. 둘은 다른 유형의 문제임을 이해하셔야 할 것 같고, 여전히 헷갈리신다면 제 생각에는 그냥 완벽한 이해를 일단 미루고 연습문제를 풀면서 코드를 계속 작성해보면 이해에 도움이 될 수 있습니다.
    • 말씀해주신 대로 지금 BFS만 10문제 넘게 풀었더니 무슨 말씀을 하신 건지 이해가 되었습니다. 역시 양치기가 답이네요. 답변해 주셔서 감사합니다><
  • VFX
    13549 숨바꼭질 3에 관해 질문드립니다

    bfs를 하기 위해서는 모든 가중치가 동일해야 한다고 들었는데

    이 코드는 2 * cur의 순서를 바꿔도 답이 다르게 나오지 않고 정상 통과 되는데
    왜 순서에 영향을 주지 않는지 이해가 가지 않아 질문드립니다

    한 번 봐주시면 감사하겠습니다

    void bfs()
    {
    dist[n] = 0;
    q.push(n);
    while (!q.empty())
    {
    auto cur = q.front(); q.pop();
    if (cur == k) break;
    for (auto& nxt : { cur - 1, cur + 1 })
    {
    if (nxt < 0 or nxt >= MX or dist[nxt] < dist[cur] + 1) continue;
    dist[nxt] = dist[cur] + 1;
    q.push(nxt);
    }
    if (2*cur < MX and dist[2*cur] > dist[cur])
    {
    dist[2 * cur] = dist[cur];
    q.push(2*cur);
    }
    }
    }
    int main()
    {
    fastIO();
    cin >> n >> k;
    fill(dist, dist + MX, 0x0f0f0f0f);
    bfs();
    cout << dist[k];
    }
    • ---
      bfs를 하기 위해서는 모든 가중치가 동일해야 한다고 들었는데

      이 코드는 2 * cur의 순서를 바꿔도 답이 다르게 나오지 않고 정상 통과 되는데
      왜 순서에 영향을 주지 않는지 이해가 가지 않아 질문드립니다
      ---

      라는 질문의 의미를 제대로 이해를 못하겠습니다. 2*cur의 순서를 바꾼다는게 무슨 의미인가요?
    • 지금 작성한 코드로는 2 * cur if문의 위치가 -1 +1 구문보다 아래에 있는데

      반대로 2 * cur가 위에 있는 경우를 얘기하고 싶었습니다

      이 문제를 풀던 도중 질문검색을 찾아보니 가중치를 고민하지 않고 그냥 작성한 BFS에서
      대부분 if문이 2 * cur, -1, +1 순으로 실행되는 경우에만 통과가 되는것으로 판단되는데
      이 코드도 가중치를 고민하지 않고 숨바꼭질 1번처럼 bfs를 작성하였는데
      조건문 순서에 영향을 받지 않고 통과가 되는것이 이해가 되지 않아 질문을 드렸습니다 : )
    • 상단의 강의 관련 질문 가이드 참고해서 질문하신 바를 바로 확인할 수 있는 코드 각각(2*cur가 위에 있는거, 아래에 있는거?)의 제출 링크 2개를 주세요. 말로만 상황을 설명하면 조금 이해가 어렵습니다.
  • 화이팅
    4179번 문제의 정답 코드에서 58번째 줄이 궁금합니다.
    if (dist1[nx][ny] != -1 && dist1[nx][ny] <= dist2[cur.X][cur.Y] + 1)
    ...
    위 코드에서 dist1[nx][ny] != -1 이 부분이 왜 필요한가요?
    • 윗 댓글 어딘가에도 이 상황에 맞는 반례가 있을텐데 모든 빈 칸을 불이 항상 방문할 수 있다고는 장담할 수 없습니다. 벽으로 인해 불과 지훈이가 분리된 상황을 고려해야 합니다.
    • 아직도 잘 모르겠습니다. 윗 댓글에 반례는 없는거 같습니다! 벽으로 인해 불과 지훈이가 분리된 상황을 고려해야 한다. 이점이 이해가 잘 되지 않습니다.

      dist1[nx][ny] <= dist2[cur.X][cur.Y] 이 조건에서 이미 dist1[nx][ny] != -1 이라는 조건이 포함된 것 아닌가요?
    • 4 4
      ###F
      #J.#
      #..#
      #..#

      이거 해보세요. 저도 강의자료 만든다고 다시 짤 때 똑같은 실수 했었어서ㅎㅎ...
  • Kysuk05
    안녕하세요 바킹독님
    문제집에 나온 문제는 아니지만 2주동안 맞왜틀을 외치다가 도저히 혼자 힘으로 해결이 안될 것 같아서 질문을 올립니다.

    문제는
    https://www.acmicpc.net/problem/2617
    구슬 찾기 문제입니다.
    알고리즘 분류는 플로이드-와샬 ,깊이 우선 탐색, 그래프 탐색이지만
    BFS + 완전탐색의 방법으로 해결하려고 하여 이 단원에 질문을 올립니다.

    파이썬으로 풀었고, 예제는 맞지만 제출하니 '틀렸습니다'가 나오는 상황입니다.
    http://colorscripter.com/s/5EWHLIr
    제출 번호는 https://www.acmicpc.net/source/40023670 입니다.

    혹시 반례나 잘못된 부분이 어디인지 알 수 있을까요?
  • 안녕하세요, 추천 문제에 있는 "16920 확장 게임" 질문합니다. 올려주신 솔루션 코드(https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x09/solutions/16920.cpp) 에서 30번째 줄에 queue.push 하는 부분이 있는데, 큐에서 인덱스로 푸시할 수 있나요? 제가 파이썬을 써서 c++을 잘 모르는 건지,구글링을 해봤는데도 인덱스로 직접 푸시하는 건 없었습니다. 제가 잘못 이해한 건가요?
  • ksb21st
    안녕하세요 바킹독님!
    백준 1697번"숨박꼭질" 을 풀다가 의문이 생겨 질문드려요!
    c++ 로

    #include <bits/stdc++.h>
    using namespace std;
    int board[200002];
    int dist[200002];
    int d[3] = {-1, 1, 2};
    int n, k;
    int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> k;
    fill(dist, dist + 200001, -1);
    queue<int>Q;
    dist[n] = 0;
    Q.push(n);
    while(!Q.empty()){
    int cur = Q.front(); Q.pop();
    for(int dir=0;dir<3;dir++){
    int nx;
    if(d[dir] == 2)nx = cur*2;
    else nx = cur + d[dir];
    if(nx == k){
    cout << dist[cur] + 1;
    return 0;
    }
    if(dist[nx] >= 0 || nx < 0 || nx > 100000) continue;
    dist[nx] = dist[cur] + 1;
    Q.push(nx);
    }
    }
    cout << dist[k];
    }

    이렇게 풀었는데, '틀렸습니다' 가 나오네요!
    그런데 아무리 생각해봐도 그 이유를 모르겠어요 ㅠㅠ
    혹시 왜 자꾸 틀렸다고 나오는걸까요?
  • enble
    바킹독님, 강의 잘 보고 있습니다!
    거리 측정 문제(미로탐색)에서 dist배열을 -1로 초기화하신 이유를 여쭤봐도 될까요?
    제가 생각하기에는 dist배열을 0으로 초기화한 다음, dist[0][0] = 1로 넣고, 가장 마지막에 출력할 때
    cout << dist[n-1][m-1]; 와 같이 출력해도 문제가 없을 것 같아서요.

    체계적인 강의 덕분에 기초가 점점 튼튼해지는 것 같아 항상 감사하고 있습니다. 언제나 행복하세요!

    (질문하면서 생각해보니 원래 거리라는게 최초 시작칸을 포함하지 않는 것 같기는 한데... 제 생각이 맞는지 틀린지 궁금합니다!)
    • 저 문제에서는 특별히 시작 칸까지 포함해서 거리를 세는데 일반적으로는 시작 칸을 포함하지 않긴 하죠. 그래서 저는 그냥 -1로 초기화하는걸 선호해요. 하지만 말씀하신 것 처럼 그냥 초기값을 0으로 두고 짜도 전혀 상관없어요.
  • bfs_5014
    bfs 5014번 질문 드립니다.

    http://boj.kr/dca00ccaeb044c618f6fafbcef202daa

    정답 코드링크는 아래 있습니다.

    https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x09/solutions/5014.cpp

    정답 코드랑 다른 점은 while문 안에서 목표점에 도잘하면 출력하고 종료하는 것이고
    정답 코드는 큐를 다 돈다음 판단하는 것 차이인데 제 풀이로 제출하면 왜 틀리는지 모르겠어서 질문드립니다.

    감사합니다.
  • SEONGHWAN
    ㅋㅋㅋㅋㅋㅋㅋ 미로찾기문제 마인크래프트 물 흐르는거 떠올리면서 풀었네요 좋은 강의 감사합니다 바킹독 선생님!
  • Jeon
    안녕하세요. 바킹독님 ! 항상 잘 보고 있습니다.
    BFS 5427번 문제를 풀다풀다 안풀려서 질문드립니다.

    현재 코드는 다음과 같이 짰습니다.
    https://www.acmicpc.net/source/42215829

    질문탭에 있는 반례도 전부 넣어보고 구글링해서 있는 반례도 전부 집어넣어 봤는데 어째 막상 제출하면 틀리기만 하네요 ㅠㅠ

    아무리 봐도 어디가 틀린건지 알 수가 없어서 질문드립니다.

    항상 강의 잘보고 있습니다. 감사합니다!

  • 리라리라
    안녕하세요 빡킹독님 미로찾기 문제의 경우 string board[102] 선언하신 걸 단순히 int로 변경해서 풀었는데 똑같은 코드라고 생각되는데 계속 무한 루프에 빠지고 맙니다.....제가 실력이 부족해 무엇이 다른지 모르겠네요...! 감사합니다!

    #include<bits/stdc++.h>
    #define X first
    #define Y second
    using namespace std;
    int board[102][102];
    int dist[102][102];
    int n, m;
    int dx[4] = { 1,0,-1,0 };
    int dy[4] = { 0,1,0,-1 };
    int main(void) {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    queue < pair<int, int>>q;
    for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
    cin >> board[i][j];
    }
    }
    for (int i = 0; i < n; i++)fill(dist[i], dist[i] + m, -1);
    q.push({ 0,0 });
    dist[0][0] = 0;
    while (!q.empty()) {
    auto cur = q.front(); q.pop();
    for (int i = 0; i < 4; i++) {
    int cx = cur.X + dx[i];
    int cy = cur.Y + dy[i];
    if (cx < 0 || cx > n || cy < 0 || cy > m)continue;
    if (dist[cx][cy] >= 0 || board[cx][cy] != 1)continue;
    dist[cx][cy] = dist[cur.X][cur.Y] + 1;
    q.push({ cx,cy });
    }
    }
    cout << dist[n - 1][m - 1] + 1;

    }
  • 안녕하세요 바킹독님 !
    BOJ 2146번 : 다리 만들기 문제 해설을 보다가 궁금한 점이 생겨 질문 드립니다!
    모든 육지에서 BFS를 돌리는 코드의 시간복잡도가 O(N4)라는 점은 이해했습니다.
    입력 데이터에 따라 O(n3),O(n4)의 시간복잡도로 나뉠 수 있다는 설명을 읽었는데,
    결국 섬의 좌표에서 BFS를 진행할 때 같은 번호의 섬이라면 pass하고 바다로 진행하기 때문에 끝쪽이 11111111 이면 시간이 덜 걸리고 10101010..이런 식이면 시간이 더 걸린다로 이해하면 될까요 .. ?
    • https://github.com/euichanhwang/basic-algo-lecture/blob/master/0x09/solutions/2146.cpp

      해설 링크입니다!
    • 네. 각 영역에서 상하좌우가 같은 섬으로 둘러쌓인 "내륙"은 그 육지에서 bfs를 시작하면 O(N^2)이 걸리는게 아니라 O(1)에 바로 종료되기 때문에 제시한 첫번째 데이터는 최대 2N개의 육지에서만 bfs가 O(N^2)이 걸리고 나머지는 다 O(1)에 끝나서 시간복잡도가 O(N^3)이 됩니다.

      반면 "표면적"을 최대한 넓히게 되면 거의 모든 육지가 bfs을 O(N^2)에 수행되도록 할 수 있어서 두 번째 데이터는 O(N^4)입니다.
    • 이해했습니다 감사합니다!
  • 안녕하세요 바킹독님. 매번 질문에 잘 답변해 주셔서 감사합니다.
    BFS 문제를 모두 풀어가면서 갑자기 시간복잡도에 대한 궁금증이 생겼는데요.

    BFS의 시간복잡도 O(NM) 에서 (N이 행, M이 열일 때)
    N이 600 , M이 600일 때 O(36000) 정도라면 O(N²)으로는 통과하기 힘들고 O(NlgN)으로는 넉넉하다고 알고 있습니다 (1강의 시간복잡도 표를 통해서)

    그런데 문제를 풀다보면, O(N²)인데도 통과된 것 같은 문제가 있습니다.
    BOJ 21736번 헌내기는 친구가 필요해 문제인데요.
    https://www.acmicpc.net/source/44285058
    제 풀이입니다. 이 풀이의 시간복잡도가 궁금합니다.

    마지막으로, 항상 좋은 강의와 답변 제공해주시는 점에 대해 대단히 감사합니다 😆좋은 하루 보내세요.
  • 안녕하세요 바킹독님!!
    BOJ 2146번 다리 만들기 문제 풀다가 궁금한 점이 있어서 질문드립니다. 마지막 부분에 가장 짧은 다리의 길이를 구할 때 저는 각각의 섬이 확장되면서 처음 만날 때가 가장 다리의 길이가 짧다고 생각해서 답을 적었는데 아무리해도 안되서 답을 보니 min 함수로 구하더라고요... 제 답변이 맞지 않는 반례를 아무리 생각해도 생각나지 않는데 제 답변이 틀린 이유를 알 수 있을까요?

    문제 링크 - https://www.acmicpc.net/problem/2146
    제 답변 - http://boj.kr/c346440fea5d4f9381280395ff09be89
    해설 링크 - https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x09/solutions/2146_1.cpp
    • http://www.secmem.org/blog/2019/03/07/코딩테스트-대비-특강/

      이 글의 59p, 60p에서 지적한 내용에서 틀린게 아닌가 싶습니다. 59p의 그림에서 진한 주황(=길이 2)과 연한 주황(=길이 3)이 있는데, 지금 길담배맛님의 코드에서는 bfs를 돌다가 연한 주황을 먼저 보게될 경우 길이가 2인게 있음에도 불구하고 3을 출력한 후 종료합니다.
    • 감사합니다!!! 계속해서 문제집의 문제를 더 풀어보다가 안풀리는 문제가 다시 생겨서 다시 질문드립니다. ㅠㅠㅠ 16920번 확장게임 문제입니다. 뭘 놓친건지 전혀 감을 못 잡겠네요 ㅠㅠㅠ

      링크 - http://boj.kr/f47ef8177a774216a481458540dd9743


      +++++++++++++++++++ 추가
      원래는 Q에서 front만 가져와서 BFS를 진행했는데 최대한 문제 조건과 비슷하게 Q에서 해당 턴에 해당하는 플레이어의 원소들을 전부 가져와서 BFS를 하니 맞았습니다 ㅠㅠㅠ 그런데 위의 코드와 아래 코드의 크게 다른 점을 못 느끼겠는데 하니씩 가져오나 전부 가져오나 결국엔 순서가 바뀌는 일은 없고 결과도 똑같을 거라고 생각되는데 위 코드와 아래 코드의 큰 차이가 뭘까요...ㅠㅠㅠ

      수정된 코드 - http://boj.kr/1cf924db463a42d2bf76bee9b8e7fc19
    • 반례입니다..!!

      4 3 2
      2 2
      1 . .
      . . .
      . . .
      1 2 .
  • 1231
    안녕하세요. BFS 문제집을 풀어보던 중 궁금증이 생겨 질문 드립니다.
    3차원 배열을 구글링으로 학습했을 때는 [높이][세로길이(행)][가로길이(열)] 로 ,
    [행][열]로 이뤄진 2차원 배열이 높이 개수만큼 쌓여있는 배열로 이해했는데, 7569번 토마토 문제나 2206번 벽 부수고 이동하기 문제를 보면 [x좌표][y좌표][높이 or 부순 벽의 개수] 로 두고 푸시더라고요. 제가 잘못 알고 있는것인지 궁금합니다.
  • jin
    영상 4분 46초에서, 큐에 노드를 (3,0), (2,1) 순서로 넣으셨는데 이 순서여야 하는 이유가 있나요? (2,1), (3,0)으로 넣어도 상관 없는건가요?

    트리구조에서 BFS를 설명할 때, 같은 depth인 노드를 먼저 확인하고 다음으로 넘어갔던것 같아, 헷갈려서 질문드립니다!
  • PSLOVER
    1926번 풀리는 게 너무 신기하고 재밌네요!ㅎㅎ 잘 이해할 수 있게 좋은 강의 만들어주셔서 너무 감사합니다ㅜㅜ
  • 안녕하세요.
    BOJ 2146 번 : 다리 만들기 문제에 대한 질문이 생겼습니다.
    https://www.acmicpc.net/source/share/ed0ad072ed8f4d50844578ba9da3016d
    예전에 포스팅하신 코딩 테스트 대비 특강에 나와있는 코드를 공부하다가 의문이 생겼는데요.
    공유된 소스 93번 라인처럼 반복문을 1부터 30까지만 돌아도 AC를 받습니다.
    제 생각으로는 N <= 100 이고, 섬의 조건이 동서남북으로 육지가 붙어있는 덩어리를 말하므로
    1 0 1 0 1 0 1 0 1 0
    0 1 0 1 0 1 0 1 0 1
    ....
    이런 경우에 섬의 개수가 최대 5000개가 생겨 1번 섬부터 5000번 섬 까지 체크해야 하는 게 맞다는 생각이 듭니다..
    제가 맞게 생각한 것인지 궁금합니다.

댓글 쓰기