반응형 알고리즘 PS/그래프 탐색2 [백준] 11725번 - 부모의 트리찾기 (Java)(○) https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net [첫번째] 1. 입력함수에서 인접행렬로 정점과 간선을 표현하자. 2. 방향이 없기 때문에 양쪽 모두 행렬로 표현해야 한다. 3. dfs 파라미터는 다음 정점 번호를 넘겨주자. 4. 1번의 루트 고정이므로 2번 정점부터 각 정점의 부모 노드가 뭔지 출력하면 된다. 5. 위의 출력 예제에서 2번 정점의 부모는 4번, 3번의 부모는 6번인 셈이다. 6. 1번부터 dfs 탐색을 해서 이미 방문한 노드가 부모인 셈이므로 그 번호를 출력하면 된다. 더보기 import j.. 2022. 9. 3. [백준] 11724번 - 연결 요소의 개수 (Java)(◎) https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 1. 연결 요소의 개수는 연결된 정점 그룹의 개수라고 생각하면 된다. 2. 방향성이 없는 그래프이므로 인접행렬로 받도록 하자. 1. 그룹화를 만드는 것이 관건이다. 메인함수에서 dfs를 호출할 때 for문을 돌려서 정점 1번부터 N번까지 돌면서 호출하자. 2. 방문배열 visited[]를 적극 활용해서 이미 방문한 정점은 스킵하자. 조.. 2022. 8. 31. 이전 1 다음 반응형
