알고리즘 스터디

• 백준 1068 트리 O
• 백준 12888 완전 이진 트리 도로 네트워크 O
• 백준 2233 사과나무 O
• 백준 1189 컴백홈 O
• 백준 2261 좋은수열 O
• 백준 19236 청소년 상어 ~

알고리즘 스터디

백준 1068 트리

• https://velog.io/@sunjoo9912/%EB%B0%B1%EC%A4%80-1068-%ED%8A%B8%EB%A6%AC

백준 12888 완전 이진 트리 도로 네트워크

• https://velog.io/@sunjoo9912/%EB%B0%B1%EC%A4%80-12888-%EC%99%84%EC%A0%84-%EC%9D%B4%EC%A7%84-%ED%8A%B8%EB%A6%AC-%EB%8F%84%EB%A1%9C-%EB%84%A4%ED%8A%B8%EC%9B%8C%ED%81%AC

백준 2233 사과나무

• https://velog.io/@sunjoo9912/%EB%B0%B1%EC%A4%80-2233-%EC%82%AC%EA%B3%BC%EB%82%98%EB%AC%B4

➖

백준 2261 좋은수열

• https://velog.io/@sunjoo9912/%EB%B0%B1%EC%A4%80-2261-%EC%A2%8B%EC%9D%80%EC%88%98%EC%97%B4

⚡백준 19236 청소년 상어

• https://velog.io/@sunjoo9912/%EB%B0%B1%EC%A4%80-19236-%EC%B2%AD%EC%86%8C%EB%85%84-%EC%83%81%EC%96%B4

📌참고자료

• 깊이 우선 탐색(DFS) 이란?
  https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html

• a 노드(시작 노드)를 방문
  -> 방문한 노드는 방문했다고 표시
• a와 인접한 노드들을 차례로 순회
  -> a와 인접한 노드가 없다면 종료
• a와 이웃한 노드 b를 방문했다면, a와 인접한 또 다른 노드를 방문하기 전에 b의 이웃 노드들을 전부 방문해야 한다
  -> b를 시작 정점으로 DFS를 다시 시작
• b의 분기를 전부 완벽하게 탐색했다면 다시 a에 인접한 정점들 중에서 아직 방문이 안 된 정점을 찾는다
  -> 아직 방문이 안 된 정점이 없으면 종료
  -> 있으면 다시 그 정점을 시작 정점으로 DFS를 시작

• 순환 호출을 이용한 DFS 의사코드(pseudocode)

void search(Node root) {
  if (root == null) return;
  // root 노드 방문
  visit(root);
  //방문한 노드를 표시
  root.visited = true; 
  // root 노드와 인접한 정점을 모두 방문
  for each (Node n in root.adjacent) {
    //방문하지 않은 정점을 찾는다
    if (n.visited == false) {
      //root 노드와 인접한 정점 정점을 시작 정점으로 DFS를 시작
      search(n); 
    }
  }
}