BOJ / 11725번 / 트리의 부모 찾기 [Go][Python3]

👩🏻‍💻 문제

11725번: 트리의 부모 찾기

---

✍🏻 풀이

🎨 Go

// https://www.acmicpc.net/problem/11725
package main

import (
	"bufio"
	"fmt"
	"os"
)

var (
	tree    [][]int
	visited []bool
)

func main() {
	reader := bufio.NewReader(os.Stdin)
	writer := bufio.NewWriter(os.Stdout)
	defer writer.Flush()

	var n int
	fmt.Fscanln(reader, &n)
	tree = make([][]int, n+1)
	visited = make([]bool, n+1)
	for i := 0; i < n-1; i++ {
		var u, v int
		fmt.Fscanln(reader, &u, &v)
		tree[u] = append(tree[u], v)
		tree[v] = append(tree[v], u)
	}
	parents := bfs()
	for i := 2; i < n+1; i++ {
		fmt.Fprintln(writer, parents[i])
	}
}

func bfs() (parents []int) {
	queue := []int{1}
	parents = make([]int, len(tree))
	for len(queue) > 0 {
		parent := queue[0]
		queue = queue[1:]
		for _, v := range tree[parent] {
			if !visited[v] {
				parents[v] = parent
				queue = append(queue, v)
				visited[v] = true
			}
		}
	}
	return parents
}

🎨 Python3

# https://www.acmicpc.net/problem/11725
import sys

def bfs():
    queue = [1]
    parents = [0 for _ in range(len(tree))]
    while len(queue) > 0:
        parent = queue.pop(0)
        for v in tree[parent]:
            if not visited[v]:
                parents[v] = parent
                queue.append(v)
                visited[v] = True
    return parents

if __name__ == "__main__":
    n = int(sys.stdin.readline())
    tree = [[] for _ in range(n+1)]
    visited = [False for _ in range(n+1)]
    for i in range(n-1):
        u, v = list(map(int, sys.stdin.readline().split()))
        tree[u].append(v)
        tree[v].append(u)
    parents = bfs()
    for i in range(2, n+1):
        print(parents[i])