BFS, DFS 활용 문제 고찰

BFS 문제를 많이 접하다 보니, BFS 문제 유형에 대해서 생각해보게 되었다.

 

나는 문제를 일반화 시키는 것을 선호한다. 만능은 없지만 정답에 가까워지기 편하기 때문이다.

 

먼저 그래프를 사용해야할 것 같다는 감이 올 때, 

그 감에 대해서 정의해보려고한다.

 

그래프 문제의 경우

1. 어디부터 어디까지 도달한다 

2. 가는 길을 묻는다

3. 가는 길의 횟수를 묻는다

4. 영역을 나눈다

5. 전염? 된다

 

이런 식의 힌트를 문제에서 제공한다. 의심의 여지없이 그래프를 사용해야하고, 그래프 탐색 알고리즘을 사용해야하는 경우가 많다. 

 

그래프 탐색 알고리즘 중 bfs를 사용해야할 때와 dfs를 사용해야할 때는 명확한데, 

각각의 특성을 고려했을때 그 문제가 어느 알고리즘으로 해결해야할지 더욱 명확해진다.

 

- 결국 bfs와 dfs는 그래프의 탐색이 목적이다. 따라서 그래프를 순회하기만 하는 문제는 bfs와 dfs 둘다 사용해도 무관하다.

- 최단거리의 경우 bfs가 간편하다.

- 순열과 조합일 경우에는, dfs를 사용한다. (노드의 순서에 대해 혹은 백트레킹이 필요한 경우)

 

 

지금까지는 bfs를 선호했기 때문에 문제 유형에 대해서 설명하려고 한다.

BFS를 활용한 문제는 

Graph 자료구조

Visited 자료구조

queue 자료구조

세가지 정의에서 보통은 결정난다.

 

일반화를 좋아하는 나는,  메모리 제약이 크지 않은 한,

graph[MAX][MAX] // 틀(방문가능여부, 방문해야할 number를 담고있음)

visited[MAX][MAX] //방문배열

ans[MAX][MAX] //최단경로나, 구역 나눈 배열을 추적하기 위함

queue<pair<int, int>> //큐의 모양 

 

의 형태로 코딩하는 것을 좋아한다.

 

자료를 담을 수 있는 것이 많을 수록, 정답을 내가 설정한 자료구조가 담고있을 확률또한 높아지기 때문이다.

 

 

하지만 메모리 제약이 팍팍한 경우, 설정한 자료구조 모두를 사용할 수는 없을 것이다.

 

그럴때마다 필요없는 자료구조의 순서를 지워나가야하는데, ans > visited > graph 순서로 지우는 경우가 많았던 것 같다. 

 

 

문제푸는 순서는 나의 경우 항상

1. 자료구조를 많이담은 bfs 구현.

2. 메모리 계산

   2.1. 메모리 가감

3. 출력 형식 확인

4. 자료구조에서 찾아 맞추기

과정을 거쳤다.

 

글을 읽으시는 분에게도 도움이 되길 바랍니다.