[정리] - The graph theory and the DFS, BFS methods - 2

 DFS는 Depth-First Search의 약자로 어떤 그래프가 있을 때, 임의의 한 정점[Vertex, Node]에서부터 시작하여 순회를 함에 있어서 한 노드의 끝까지 갔다가 Backtracking을 하는 알고리즘입니다. 그렇다면 BFS라고 불리는 Breadth-First Search는 어떠한 알고리즘일까요? 이는 Queue을 이용하여 문제를 푸는데 많은 도움을 줍니다. 저는 왜 Queue을 써야하는지 왜 그런 식으로 코드를 짜서 문제를 푸는지 이해하는데 많은 어려움을 겪었습니다.

일단 Queue자체는 Insertions(push)과 Deletions(pull or pop)이 상수 시간 내에 동작한다는 특징을 갖고 있습니다. 그렇기 때문에 어떤 연결된 그래프, Spanning Tree을 순회하기 위해서는 정점과 연결된 간선의 개수만 고려하면 충분하기 때문에 대체로 O(V+E)의 Running time을 갖습니다. V = the number of vertices E = the number of Edges;

IterativeBFS는 IterativeDFS을 stack에서 Queue로만 바꾸면 됩니다. 참 놀랍습니다.

figure 1a

스택의 논리를 바꾸기만 하면 왜 Queue가 너비를 우선적으로 탐색합니다. 개인적으로 이 부분을 이해하는데 약간의 어려움이 있었습니다. 어떤 정점 u의 successor들을 우선적으로 Queue에 넣으면 while문을 돌면서 pop을 할 때,  정점 u에 인접한 정점들이 우선적으로 튀어나옵니다. 따라서, 어떤 정점 u의 인접한 정점 v을 먼저 검증하고, 이 v에 연결된 정점들을 Queue에 Push하게 되면, u에 인접한 정점들보다 후순위의 입장에서 Queue에 삽입이 됩니다. 이 외에는 크게 어려움이 없습니다. 진짜 어려움은 이런 논리들을 어떤 문제를 해결할 때 어떻게 활용할 지 결정하는 부분이라고 생각합니다.

백준 알고리즘 사이트에 게시가 되어 있는 한 문제를 참고했습니다. 7576번 문제로 이전 문서에서 보았던 제가 작성한 코드의 약점인 "모든 Subgraph들을 탐색할 수 없는 문제점"을 정확하게 짚어낸 문제입니다.

figure 1b

첫 줄에 상자의 크기가 결정됩니다. 그리고 두 번째 줄부터는 상자에 저장된 토마토의 정보들이 정수의 형태로 하나씩 주어집니다. 

0은 익지 않은 토마토, 1은 익어버린 토마토, -1은 토마토가 없는 칸을 나타냅니다. 이 문제에서는 어떤 지점에서 그래프를 순회할지 명확하게 주어져 있습니다. 익은 토마토로부터 시작하여 인접한 익지 않은 토마토들이 영향을 받기 때문에 익은 토마토인 (1)을 기준으로 순회를 하면 됩니다. 

이 부분이 문제입니다. 익은 토마토는 상자 어디든 있을 수 있습니다. 즉, 하나 이상의 순회 출발점을 갖는다는 뜻이며 단일 그래프를 순회하는 문제가 아닌 하나 이상의 그래프를 순회하는 문제입니다. 제 코드는 단일 그래프만 순회할 수 있었습니다. 그 대안으로 모든 정점들을 출발선에 놓고 순회를 시킨다는 안을 내놓았는데 다행히 이 문제는 그런 수고를 들일 필요는 없습니다. (1)로 표기된 지점들만 골라서 출발을 시키면 풀 수 있기 때문입니다.

My Solution

저는 몇 가지 DFS, BFS문제들을 풀면서 정형화된 입력 형식이 있다고 생각했습니다. 하나는 간선[Edges]들을 입력으로 주는 경우, 다른 하나는 아예 그래프를 행렬의 형태로 주는 경우입니다. 물론 더 많은 입력의 형태가 존재합니다. 하지만 경험이 부족한 탓에 현재는 이 정도의 타입만 확인할 수 있었습니다.

먼저 입력부터 생각을 해봤습니다. N개의 Row, M개의 Column에 대한 정보를 1, 0, -1의 형태로 줍니다. 이 정보를 어떻게 관리하면 좋을까, vertices[노드 번호][노드에 연결된 것들]형태로 만들어도 될 것 같았지만 직관적이지도 않고 복잡하다고 생각했습니다. 그냥 M by N 행렬에 각각 Vertex라는 형태의 Class을 만들어 박아 넣는 것이 편리하다고 결론 내렸습니다. 이렇게 입력 값을 관리하면 아주 좋은 장점이 하나 있습니다.

figure 2a

Enumeration class을 도입하여 문제를 풀 때 헷갈리지 않도록 했습니다. 익은 토마도는 Ripe, 익지 않았으면 Not_Ripe, 토마토가 없거나 기타 다른 상황엔 None을 부여할 것입니다. Vertex Class의 세세한 부분은 알고리즘 보다는 C++의 다른 문서들을 참조하는 편이 나을 것 같습니다. rvalue/lvalue referenece, function overloading, std::move등의 C++ 지식이 조금 있으면 좋습니다. 가장 중요한, 무조건 있어야 하는 것은 Vertex의 좌표인 x, y그리고 Vertex 자리에 존재하는 토마토의 상태를 나타내는 tomato입니다. 그리고 7576번 문제를 흉내 내기 위해서 다음과 같은 무작위 토마토 상자 생성 함수를 만들었습니다.

figure 2b

상자의 크기를 결정하는 것은 자유입니다. 하지만 전과 같은 이유로 적당히 제한했습니다. 이렇게 짠 코드를 콘솔에서 확인을 하기 위해 다음과 같은 인쇄 함수를 만들고 몇 번 돌려보면 대강 뼈대는 만들었다는 느낌을 받을 수 있습니다.

figure 2c

이것저것 인쇄를 해보며 테스트를 해야 하기 때문에 가장 보편적으로 사용할 수 있도록 iterator을 사용해서 구현했습니다. 이제 print 함수는 이것만 있으면 되며 다른 타입의 컨테이너를 만든다면 iterator을 반드시 내장 시켜야 합니다. 몇 번 테스트를 해보면 다음과 같이 적당한 문제를 만들어 낼 수 있습니다.

figure 2d-1

figure 2d-2

figure 2d-3

이제 문제를 만들었으니 해결하는 함수를 짜 볼 차례입니다. 문제를 풀 때 주의해야 할 점이 몇 가지 있습니다. 익은 토마토는 대각선을 제외한 인접한 토마토들을 한 차례에 한 번만 익힐 수 있다는 것, 익은 토마토는 어디든 있을 수 있다는 점 등등입니다. 따라서, 우리가 일반적으로 배우는 BFS을 응용하지 않으면 풀 수가 없습니다. 

Major issues

모든 그래프를 순회하지 않는 점을 해결하는 것은 어렵지 않습니다. 익지 않은 토마토의 정점들을 모아서 순차적으로 순회를 시켜 해결할 수 있기 때문입니다. 하지만 이 문제는 모든 토마토가 익는데 어느 정도의 시간이 필요한지 묻고 있습니다. 이 시간을 어떻게 세면 좋을지 떠올리는 것이 어려웠습니다.

figure 3a

빨간 원이 익은 토마토이며 까만 원이 익지 않은 토마토라고 생각해 봤습니다. 오른쪽처럼 BFS을 사용하면 순회를 할 것입니다. 만약 방문을 할 때마다 날짜를 세면 BFS가 끝났을 때, 순회한 모든 개수가 나와버립니다. 즉, 실제로는 총 2일이 걸리지만 순회하는 노드마다 날짜를 세면 총 4가 나와버립니다. 

제가 원하는 논리는 이전 토마토가 익는 순간의 날짜에 +1을 더해서 현재 검증하는 토마토가 익는 날짜를 구하는 것입니다. 생각해보면 마치 Dynamic Programming과 닮았다고 여겨집니다. 이전에 받았던 값을 그대로 불러와서 쓰는 것입니다.

figure 3b

문제를 해결하기 위해 몇 가지 준비를 해야 합니다. box는 입력으로 받은 토마토 상자의 상태를 저장하기 위한 컨테이너 입니다. Queue는 BFS을 위한 Queue이며 days는 각 토마토가 익는 순간의 날짜를 격납하고 다음 토마토가 익었을 때, 이전 날짜에 1을 더해서 저장하기 위한 컨테이너 입니다. begin은 입력으로 받은 토마토 중에서 이미 익어 있는 토마토들을 골라서 순회의 출발점으로 사용하기 위한 장치입니다.

figure 4c

figure 4d-1

Solution에 진입하면 가장 먼저 사용할 정보들을 정리합니다. 안 해도 되는데 한 번 정리를 해보았습니다. 실질적으로 어떤 효용이 있을지 모르겠습니다. 대신 Iterator을 사용하여 정보를 출력할 때 깔끔하게 인쇄된다는 장점이 있습니다. 제가 생성한 임의의 토마토 상자들을 Vertex로 변환하여 격납할 컨테이너 box, 경과한 날짜를 기록할 days를 입력된 컨테이너에 알맞게 조정합니다.

for loop에 진입하면 생성된 입력인 generated_box에서 위치 정보들을 뽑아서 box에 입력합니다. zero-based이기 때문에 Vertex에 +1을 하고 있습니다. 범위를 벗어난 컨테이너 접근에 늘 유의해야 합니다.

figure 4d-2

case 1을 보면 begin vector에 Vertex instance을 넣는 모습이 보입니다. 입력 단계에서 이미 익어 있기 때문에 이 토마토는 순회의 시작으로 쓰이게 됩니다.

figure 4d-3

이제 이 시작점들을 Queue에 삽입합니다. 이렇게 하면 익은 토마토 정점 u, v, r .. ... 에 인접한 토마토들은, 익은 토마토에 u,v,r,..,에 인접한 토마토들부터 익히고 나서 검사를 받습니다. u에 연결된 토마토들은 v, r, ... 다음에 검증 순서를 기다리고, v에 연결된 토마토는 r , ... , u에 연결된 토마토 다음에 검증 순서를 기다립니다. 유심히 생각해보면 u, v, r에 연결된 토마토들이 번갈아가며 차례대로 검증을 받는다는 사실을 알 수 있습니다. 

figure 4e

figure 4f-1

이 부분이 실질적으로 계산을 하는 부분입니다. 알고리즘 자체를 외우고 타이핑 하는 건 중요하지 않다고 생각합니다. BFS, DFS의 큰 틀 안에서 주어진 문제를 해결하기 위해서 어떻게 응용해야 하는지 파악하는 것이 어렵고 중요합니다. 매번 조건을 만족하는 Vertex에 진입할 때마다, Predecessor의 날짜 값에 1을 더해서 현재 Vertex에 저장해주는 것이 정말 중요합니다. 

이후로는 크게 볼 것이 없습니다. days에서 가장 큰 값을 추출해서 정답으로 내놓으면 끝이기 때문입니다.

만약, 토마토가 삼차원 공간에 존재한다면 z축만 추가해주면 그만입니다.