TIL - 20.12.25 (DFS, BFS, 위상정렬)

❄️ 11725번 - 트리의 부모 찾기

크리스마스니까 트리의 부모 찾기 문제를 풀었다.
bfs, dfs 모두 가능한 문제
아직은 bfs, dfs가 익숙하지 않아서 모든 문제에 대해 visited 리스트를 만들고 방문 여부를 체크해주는데 이 문제에서는 단순히 부모만 확인해주면 되기 때문에 방문 여부를 확인해줄 필요가 없었다.
방문하면서 아직 부모가 결정되지않은 노드의 부모만 결정해주면 해결할 수 있다.
(부모 노드 결정 여부로 방문 여부까지 확인할 수 있음)

❄️ DFS 주의사항

안 이어져 있는 정점은 한 번의 DFS로 방문할 수 없다.
한 컴포넌트 안에 속한 정점은 서로 모두 이어져 있다. 연결 그래프는 컴포넌트가 단 하나인 경우 (모든 정점들이 연결된 상태)
DFS를 한 번만 하면 시작점의 컴포넌트만 방문하고, 나머지는 방문할 수 없다. 컴포넌트가 여러 개인 경우, 모든 정점을 방문하고 싶다면 반복문을 돌면서 방문하지 않은 정점에 대해 DFS를 수행해줘야 한다. -> 방문 시도 횟수가 컴포넌트의 개수

❄️ BFS

각 단계의 정점들은 그 안에서 순서가 바뀔 순 있지만, 다른 단계와는 섞이지 않는다.
n단계에 방문하는 정점들은 시작점으로부터 최단거리가 모두 n 이므로 최단거리 구하는 문제에 사용한다.

❄️ 위상 정렬

사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것
1. 진입차수(Indegree) : 특정 노드로 들어오는 간선의 수
2. 진출차수(Outdegree) : 특정 노드에서 나가는 간선의 수

• 동작 순서

1. 진입차수가 0 인 모든 노드를 큐에 넣는다.
2. 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거한다.
3. 새롭게 진입차수가 0이 된 노드를 큐에 넣는다.
   2번과 3번을 큐가 빌 때까지 반복한다.
   큐에서 나온 애들로 리스트 만들면 위상 정렬 결과

• 위상정렬은 정답이 여러 개일 수도 있다.
  한 단계에 해당되는 노드가 여러 개일 경우에 따라 나뉜다.

• 모든 원소를 방문하기 전에 큐가 빈다 => 사이클이 존재한다