그래프 DFS - 문제1 감시 카메라

이한울·2019년 7월 8일
0

그래프

목록 보기
15/17

문제 파악

그래프의 한 정점에서 인접한 정점끼리는 감시 카메라를 공유하는데, 이 때 모든 갤러리를 감시하는 감시 카메라의 최소 대수를 구하는 문제이다. 직관적으로 생각했을 때는 정점 별로 감시 카메라를 둔다고 가정했을 때 인접 정점들을 확인하면서 감시 카메라가 설치 되었는지 안되었는지를 체크 하면서 하나씩 늘려나가야 되는데 그 시작점을 설정하는 것도 그렇고 한 정점씩 확인한다고 했을 때 지금 선택한 결정이 다른 시작점에서 봤을 때는 비효율적인 결정이 될 수 있다는 부분을 어떻게 처리할 지를 어떻게 접근할 지 생각하지 못했다.

문제 풀이

이 문제의 핵심 부분은 관람한 갤러리를 다시 가기 위해서는 이전에 지나 왔던 복도를 반드시 한 번 이상 지나야 하는 구조라는 것이다. 이 구조의 의미는 이 그래프는 사이클이 존재하지 않는다는 것이다. 사이클이 존재하지 않는 다는 것은, 이 그래프의 연결된 갤러리들은 트리 구조를 이룬다는 것이다. 이 문제의 경우 시작점이 명시되어 있지 않기 때문에 루트 없는 트리 구조이다.
루트 없는 트리 구조라는 점을 알게 되면 문제 풀이는 훨씬 간단해진다. 한 번 dfs를 시행해서 만들어 지는 스패닝 트리는 dfs를 시작한 지점을 루트로 트리가 만들어지는 데, 리프 노드 부터 감시 카메라의 존재 여부를 체크 하면서 올라 가면 문제가 간단히 해결 된다. 리프 노드는 자식이 존재하지 않고 부모는 존재하기 때문에 감시 카메라를 설치할 필요가 없다. 리프 노드 이외의 노드는 자식 노드가 감시 카메라가 설치되어 있지 않으면, 반드시 감시 카메라를 설치해야 되고 자식 노드가 설치되어 있으면 자신은 이미 감시 상태이기 때문에 감시 카메라를 설치할 필요가 없다.

트리 구조로 보았을 때 문제가 풀리는 이유는 문제가 훨씬 단순해지기 때문이다. 트리가 아닌 그래프 즉 사이클이 존재하는 그래프일 때는 부모 자식 관계가 존재하지 않기 때문에 한 노드의 인접 노드를 분류할 수 없게 되어 여러 노드가 접근하는 상황에서 감시 카메라의 설치 여부를 따지는 것이 훨씬 복잡해진다. 그러나 트리 구조로 접근할 경우 한 노드의 부모와 자식 관계만 확인하면 되기 때문에 (여기서는 자식을 기준으로 카메라 설치를 결정한다) 위계 질서를 기준으로 문제를 순차적, 재귀적으로 접근함으로써 문제가 훨씬 단순해지는 것이다.

느낀 점

문제에서 트리 구조를 캐치할 수 있는 부분은 연결된 그래프 내에서 사이클이 존재하지 않는다, 간선의 개수가 V-1개이다, 두 정점을 연결하는 단순 경로가 정확히 하나이다(돌아갈 경우 반드시 같은 경로로 가야 한다).
이와 같은 설명이 있을 경우 트리 구조로 문제를 축소 해 복잡도를 훨씬 줄일 수 있다.

profile
Backend Engineer 이한울입니다

0개의 댓글