[Graph] ‘그래프 탐색’에 대한 고찰

‘그래프 탐색’에 대해 새로운 부분을 발견할 때마다 업데이트합니다.

‘그래프 탐색’에 대한 고찰

그래프 탐색은 다음과 같이 나눌 수 있다.

단순 탐색

• dfs: 모든 경우 탐색, 백트래킹
  • 백트래킹 코드에 조건을 추가하면 T자 탐색이 가능하다.
    • 14500. 테트로미노
  • 백트래킹 알고리즘의 핵심은 ‘유망성 검사(가지치기, pruning)’이다. 적절한 유망성 검사는 시간을 크게 단축시킨다.
• bfs: 최단거리, 연결 요소 탐색
  • 정해진 목적지 없이 목적지 후보들만 있을 때, 목적지 후보들 중 최단 거리의 목적지를 찾는 용도로 사용할 수 있다.
    • 16236. 아기상어
• floyd-warshall: 모든 노드 간 최단 거리

최적 탐색

• dijkstra: 최단 거리 + 가중치 존재
• bellman-ford: 최단 거리 + 음수 가중치 존재
  • 벨만포드 알고리즘을 수행하고 나면 시작 정점에서 다른 정점으로의 최단 거리를 알거나, 그래프 내에 있는 음수 사이클의 존재성을 알 수 있다.
    • 11657. 타임머신
  • 음수 사이클이란 사이클 상의 모든 가중치가 음수라는 것이 아니다. 사이클 상의 음수 가중치의 합이 양수 가중치의 합보다 그 절댓값이 클 경우, 거리를 무한히 음수로 만들 수 있기 때문에 음수 사이클이다.
    • 즉, 음수 사이클이란 거리(또는 시간, 사이클 상의 가중치들의 합)를 무한히 음수로 만들 수 있는 경우를 뜻하고, 이 경우에는 다른 정점으로의 최단 거리를 구할 수 없다.
    • 음수 가중치를 가지는 간선은 무조건 방향을 가져야 한다. (아니면 무조건 음수 사이클이 됨)
  • 정해진 출발지 없이 음수사이클의 존재성만을 따질 때도 벨만포드 알고리즘을 사용할 수 있다.
    • 이 경우, 출발지가 있을 때와 코드 상에서 2가지 변경이 필요하다.
    • 1865. 웜홀