백준 11728번: 트리의 부모 찾기

문제

https://www.acmicpc.net/problem/11728

11728번: 배열 합치기

---

풀이

루트 없는 트리가 주어진다. 트리의 루트를 1이라고 정했을 때 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력하는 문제입니다.

---

접근

이진트리라는 조건도 없고 자식노드가 부모노드보다 숫자가 크거나 작다는 조건이 없기 때문에 일반적인 이진탐색트리 관련 알고리즘으로는 문제를 해결할 수 없었습니다. 그래서 DFS와 BFS를 이용하여 그래프를 순회하며 각 노드의 부모노드를 1차원 배열에 저장해가 문제를 해결했습니다.

---

코드

자바(BFS)

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Queue;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {

    static int[] parent;
    static ArrayList<Integer>[] list;

    public static void bfs() {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(1); // (1)
        parent[1] = 1;
        while (!queue.isEmpty()) {
            int p = queue.poll(); // (2)
            for (int e : list[p]) { // (3)
                if (parent[e] == 0) {
                    parent[e] = p;
                    queue.offer(e);
                }
            }
        }
    }

    @SuppressWarnings("unchecked")
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        parent = new int[n + 1];
        list = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) {
            list[i] = new ArrayList<Integer>();
        }
        for (int i = 0; i < n - 1; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            list[x].add(y);
            list[y].add(x);
        }
        bfs();
        StringBuilder sb = new StringBuilder();
        for (int i = 2; i <= n; i++) {
            sb.append(parent[i]).append("\n");
        }
        System.out.println(sb);
    }
}

int형 배열 parent는 각 노드의 부모노드를 저장합니다. 예를 들어 루트노드 1의 부모노드는 존재하지 않기 때문에 parent[1]은 1로 초기화합니다.

ArrayList 배열 list의 원소는 각 노드에 연결된 노드를 의미하며 노드가 연결돼있는 정보를 입력받고 각 노드의 ArrayList에 해당 노드를 add합니다. 이후 bfs 메소드를 실행합니다.

 

(1) 루트노드 1을 큐에 삽입한 후에 parent[1]을 1로 초기화합니다.

앞서 설명하였듯이 루트노드 1의 부모노드는 존재하지 않기 때문에 parent[1]은 1로 초기화합니다. 아직 방문하지 않은 x번 노드의 부모노드는 아직 알 수 없기 때문에 parent[x] = 0이며 이를 구분하기 위해서 입니다.

 

(2) 큐에서 poll한 현재 노드를 의미하는 int p

p번 노드에 연결된 다른 노드를 확인하기 위해 foreach문을 활용합니다. list[p]에 들어있는 원소들은 p의 자식노드들입니다. 그 이유는 루트노드인 1부터 탐색을 시작했기 때문에 1에 연결된 노드들은 1의 자식노드들이고 그 이후에 각 노드들에 연결된 노드들 또한 해당 노드의 자식노드들이기 때문입니다.

 

(3) foreach문을 사용한 list[p]의 원소 e

e의 부모노드 parent[e]가 0이라면 아직 탐색하지 않은 노드이기 때문에 parent[e] = p로 초기화한 후에 큐에 e를 삽입합니다.

 

bfs 함수가 종료되면 2번 노드부터 n번 노드까지 순서대로 각 노드의 부모노드를 출력하기 위해 for문을 이용하여 parent[i]를 Stringbuilder sb에 함께 저장했다가 한꺼번에 출력합니다.

C언어(DFS)

#include <stdio.h>
#include <stdlib.h>
int n, *parent, *visited;
typedef struct node {
	int data;
	struct node* next;
} node;
void add(node* target, int data) {
	node* now = (node*)malloc(sizeof(node));
	now->data = data;
	now->next = target->next;
	target->next = now;
	return;
}
node* list[100001];
void dfs(int idx) {
	if (visited[idx]) { // (2)
		return;
	}
	visited[idx] = 1;
	node* curr = list[idx]->next;
	while (curr != NULL) { // (3)
		if (!visited[curr->data]) {
			parent[curr->data] = idx;
			dfs(curr->data);
		}
		curr = curr->next;
	}
}
main() {
	scanf("%d", &n);
	parent = (int*)malloc(sizeof(int) * (n + 1));
	visited = (int*)malloc(sizeof(int) * (n + 1));
	for (int i = 1; i <= n; i++) {
		parent[i] = visited[i] = 0;
		list[i] = (node*)malloc(sizeof(node));
		list[i]->next = NULL;
	}
	for (int i = 0; i < n - 1; i++) {
		int x, y;
		scanf("%d %d", &x, &y);
		add(list[x], y);
		add(list[y], x);
	}
	for (int i = 1; i <= n; i++) {
		dfs(i); // (1)
	}
	for (int i = 2; i <= n; i++) {
		printf("%d\n", parent[i]);
	}
}

자바를 이용한 풀이와 다르게 BFS가 아닌 DFS를 사용한 풀이입니다.

ArrayList 배열 list는 ArrayList 배열은 연결리스트를 이용하여 구현했습니다.

 

(1) for문으로 1번부터 n번 노드까지 dfs(i)를 실행합니다.

dfs 함수의 매개변수 idx는 현재 탐색중인 노드 번호를 의미합니다.

 

(2) visited[idx]가 true인 경우 return합니다.

(1)의 for문에서 i번 노드가 이미 방문했던 노드일 수도 있는데 방문 여부를 확인하지 않는 이유는 dfs 함수 내부에서 시작할 때 방문 여부를 확인하고 return하기 때문입니다. 방문하지 않은 노드라면 visited[idx]를 1로 초기화하고 다음을 수행합니다.

 

(3) idx의 노드에 연결된 모든 노드를 탐색합니다.

node* curr은 idx번 노드에 연결된 노드를 의미합니다. node 구조체에서 해당 노드의 번호는 data입니다. visited[curr->data]가 false인 경우 parent[curr->data] = idx로 초기화한 후에 dfs(curr->data)를 재귀적으로 실행합니다.

 

모든 함수가 종료되면 2번 노드부터 n번 노드까지 순서대로 각 노드의 부모노드를 출력하기 위해 for문을 이용하여 parent[i]를 출력합니다.

---

결론

위의 문제의 경우는 BFS보다 DFS가 효율적이라고 생각됩니다. 그 이유는 DFS는 BFS와 달리 for 문으로 여러 번 호출해야 하지만 구해야 하는 해가 최적의 해가 아닌 단지 각 노드의 부모 노드만 기록하면 되기 때문입니다.
제가 잘못 생각하는 것일 수도 있지만 이런 식으로 같은 문제를 여러 가지 알고리즘을 풀면서 프로그래밍적 사고 능력을 키울 수 있을 것 같다는 생각이 들었습니다.