DFS의 활용과 Backtracking(백트래킹)

14502번: 연구소

백준 14502번 문제를 풀면서 필요한 개념을 정리하고자 한다.

 

DFS ( Depth First Search : 깊이 우선 탐색 ) 의 개념

그래프 전체를 탐색하는 방법 중 하나로,

시작 노드 부터 다음 branch로 넘어가기 전에 해당 branch를 완벽하게 탐색하는 방법.

DFS의 활용

주로 역량 테스트에서 사용되는 방식으로,

1. 그래프를 모두 탐색

2. 특정 조합 구하기/순열

DFS로 조합 구현

위 그림을 보면 DFS 알고리즘을 이용해서 집합 {1, 2, 3}의 모든 조합을 구할 수 있다.

만약, 여기서 특정 조건을 둔다면? -> 특정 조합을 구할 수 있음, 백트래킹과 연관 지을 수 있다!

 

Backtracking

DFS를 사용해서 만약에 조건에 맞지 않으면 바로 중단하고 이전으로 돌아가서 다시 다른 경우를 탐색하는 알고리즘. 

여기서 중요한 것은, 이전으로 돌아가서 다시 탐색하기 때문에 이전 상태로 원상복구 시켜줘야 한다는 것!!

순열이라면 그 전 상태로 돌아가서 순열을 출력해야 하므로, queue에서 pop을 다시 한다던지 방문상태를 다시 false로 바꾼다던지 말이다.

백준 14502문제에서 이를 적용할 수 있다. 다음계속!!!

 

참고

[파이썬으로 시작하는 삼성 SW역량테스트] - 7. DFS와 BFS의 활용