dfs

💻 Problem문제 보러 가기  루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. 첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다. 첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.  💡 Approach사실 처음에는 복잡하게 생각해서 코드 짜기 헷갈렸다...2번부터 n번까지의 노드를 출력하려면 2 ~ n 반복문으로 탐색 함수를 돌려서 각 결과를 출력하는 건 줄 알았다.그래서 연결된 노드 중에 루트 노드가 있으면 루트 노드가 부모 노드이고.. 연결된 노드가 하나이면 연결된 노드가 부모 노드이고.. ..

💻 Problem문제 보러 가기 텔레토비 동산에 사는 너구리 구구는 입구, 거실, 주방, 안방, 공부방, 운동실, 음악실, 음식 창고 등 N개의 방을 가지고 있다. 입구를 포함한 모든 방은 1부터 N까지의 번호가 있고, 입구는 1번이다.  구구의 집으로 들어가는 입구는 한 개이며 입구와 모든 방들은 총 N-1개의 길로 서로 오고 갈 수 있다.구구는 스머프 동산에서 멜론아 아이스크림을 발견했다. 구구는 무더운 여름 햇살을 피해 최대한 입구에서 먼 방에 아이스크림을 숨기려고 한다.구구가 집 입구에서 멜론아 아이스크림을 숨기려고 하는 방까지 이동하는 거리를 구하여라. 💡 Approach처음에 이 문제를 봤을 때 간선에 가중치가 있으니 다익스트라 문제 아닌가? 싶었다.하지만 다익스트라는 최단 거리를 찾는 알..

💻 Problem문제 보러 가기  방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.  💡 Approach간선 정보(간선의 양 끝점)를 입력받고 있기 때문에 간선 정보를 가지고 graph를 만들어야 한다.만든 그래프를 바탕으로 정점 1부터 그래프 탐색을 시작한다. 만약 연결 요소가 하나인 그래프라면 첫 탐색에서 모든 정점에 방문 처리가 됐을 것이다.하지만 연결 요소가 2 이상인 그래프라면 첫 탐색 이후에 방문 처리가 되지 않은 정점이 있을 것이다.그렇게 방문 처리 되지 않은 정점을 찾아서 해당 정점을 기준으로 그래프 탐색을 하는 것을 반복하여 그래프 탐색을 몇 번했는지 세면 된다. 아래는 연결 요소에 대한 이해를 돕기 위한 필기이..