반응형
● 문제 접근 과정
1. 첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.
2. 첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.
3. 트리와 연결리스트를 이용하여, 두 노드를 연결하는 간선을 인접리스트에 추가. (add_edge)
4. 인접한 노드를 재귀적으로 방문하여, 부모노드를 parent배열에 저장. ( 부모 노드를 기록한 노드는 제외 , dfs)
5. parent 배열을 출력.
● 구현
#include <stdio.h> // 표준 입출력 라이브러리 포함
#include <stdlib.h> // 표준 라이브러리 포함 (동적 메모리 할당을 위해 사용)
#define MAX_NODES 100001 //노드의 최대 개수를 정의
// 연결 리스트의 노드를 나타내는 구조체
typedef struct Node {
int data; // 노드 번호
struct Node *next; // 다음 노드를 가리키는 포인터
} Node;
Node *adj_list[MAX_NODES]; // 인접 리스트를 나타내는 배열
int parent[MAX_NODES]; // 각 노드의 부모를 저장할 배열
int visited[MAX_NODES]; // 각 노드의 방문 여부를 체크할 배열
// 노드 u와 노드 v를 연결하는 간선을 인접 리스트에 추가하는 함수
void add_edge(int u, int v) {
Node *node = (Node *)malloc(sizeof(Node)); // 새로운 노드를 동적 할당
node->data = v; // 노드 번호를 설정
node->next = adj_list[u]; // 현재 u의 인접 리스트의 첫 노드를 다음 노드로 설정
adj_list[u] = node; // u의 인접 리스트의 첫 노드를 새로 만든 노드로 갱신
}
// 현재 노드를 방문하고, 인접한 노드를 재귀적으로 방문하여 부모 노드를 기록하는
// 함수
void dfs(int node) {
visited[node] = 1; // 현재 노드를 방문했다고 표시
Node *cur = adj_list[node]; // 현재 노드의 인접 리스트의 첫 노드를 가져옴
while (cur != NULL) { // 인접 리스트의 끝까지 반복
if (!visited[cur->data]) { // 인접한 노드가 방문되지 않았다면
parent[cur->data] = node; // 인접한 노드의 부모를 현재 노드로 설정
dfs(cur->data); // 인접한 노드를 재귀적으로 방문
}
cur = cur->next; // 다음 인접한 노드로 이동
}
}
int main() {
int N;
scanf("%d", &N); // 노드의 개수를 입력받음
// N-1개의 간선 정보를 입력받아 인접 리스트를 구축
for (int i = 0; i < N - 1; i++) {
int u, v;
scanf("%d %d", &u, &v); // 간선 정보를 입력받음
add_edge(u, v); // 노드 u와 노드 v를 연결
add_edge(v, u); // 노드 v와 노드 u를 연결 (무방향 그래프)
}
dfs(1); // 루트 노드(1)부터 시작하여 DFS 탐색
// 각 노드의 부모를 출력 (노드 2부터 N까지)
for (int i = 2; i <= N; i++) {
printf("%d\n", parent[i]);
}
return 0;
}
https://www.acmicpc.net/problem/11725
반응형