출처: [백준] 2865번 나는 위대한 슈퍼스타K

문제

상근이는 한국 최고의 가수를 뽑는 “나는 위대한 슈퍼스타K”의 감독이다. 상근이는 다음과 같이 참가자를 선발하려고 한다.

“나는 위대한 슈퍼스타K”의 예선에는 N명이 참가했고, 서로 다른 M개 장르에 대한 오디션을 보았다. 심사위원은 모든 참가자의 각 장르에 대한 능력을 점수로 매겼다. 이 점수는 실수로 나타낸다.

본선에는 총 K명이 나갈 수 있다. 각 참가자는 본선에서 단 하나의 장르만 부를 수 있고, 이 장르는 상근이가 정해준다. 한 사람이 여러 장르를 부를 수는 없지만, 여러 사람이 같은 장르를 부를 수는 있다.

모든 참가자의 각 장르에 대한 능력이 주어진다. 이때, 능력의 합이 최대가 되도록 참가자와 장르를 선택하는 프로그램을 작성하시오.

입력

첫째 줄에 N, M, K가 주어진다. (1 ≤ M ≤ 100, 1 ≤ K ≤ N ≤ 100)

다음 M개의 줄은 각 장르에 대한 참가자의 능력이 주어진다. 이 줄에는 N개의 (i, s)쌍이 주어진다. 여기서 i는 참가자의 번호, s는 그 참가자의 장르에 대한 능력이다. 이 쌍은 능력이 감소하는 순서대로 주어진다. 참가자의 번호는 1부터 N까지 이다.

각 줄에 모든 학생은 한 번씩 등장한다.

출력

첫째 줄에 본선 참가자의 능력의 합을 소수점 첫째자리까지 반올림해 출력한다.

예제 입력 1

1
2
3
4
5

4 4 3
4 5.0 2 4.0 3 2.0 1 1.0
2 2.0 3 1.0 1 0.5 4 0.3
4 6.0 3 5.0 2 2.0 1 0.0
1 4.0 2 3.0 4 0.6 3 0.3

예제 출력 1

1

15.0

출처

• Contest > Croatian Open Competition in Informatics > COCI 2010/2011 > Contest #3 3번
  • 문제를 번역한 사람: baekjoon

알고리즘 분류

• 자료 구조
• 그리디 알고리즘
• 정렬
• 우선순위 큐

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

import sys

input = sys.stdin.readline

N, M, K = map(int, input().split())

skills = {}

for i in range(N):
    skills[i + 1] = 0

for i in range(M):
    genre = list(map(float, input().split()))

    for j in range(0, N * 2, 2):
        if genre[j + 1] > skills[genre[j]]:
            skills[genre[j]] = genre[j + 1]
    # print(skills)
score = sorted(list(skills.values()), reverse=True)
# print(score)
total_sum = sum(score[:K])
print('%.1f' % total_sum)

출처: [백준] 7562번 나이트의 이동

문제

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

입력

입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.

각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, …, l-1} × {0, …, l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.

출력

각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다.

예제 입력 1

1
2
3
4
5
6
7
8
9
10

3
8
0 0
7 0
100
0 0
30 50
10
1 1
1 1

예제 출력 1

1
2
3

5
28
0

출처

• University > Tu-Darmstadt Programming Contest > TUD Contest 2001 3번
  • 문제를 번역한 사람: baekjoon
  • 데이터를 추가한 사람: sait2000
  • 문제의 오타를 찾은 사람: sgchoi5

링크

• PKU Judge Online
• TJU Online Judge

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

import sys
from collections import deque

input = sys.stdin.readline

T = int(input())

# 나이트가 이동할 수 있는 8가지 방향 정의
steps = [(-2, -1), (-2, 1), (2, -1), (2, 1), (-1, -2), (-1, 2), (1, -2), (1, 2)]


def BFS(graph, start):
    queue = deque([start])

    while queue:
        # 큐에서 하나의 원소를 뽑아 출력하기
        r, c = queue.popleft()
        if r == target_row and c == target_column:
            return graph[r][c]
        for step in steps:
            # 이동하고자 하는 위치 확인
            next_row = r + step[0]
            next_col = c + step[1]
            # 해당 위치로 이동이 가능하다면 카운트 증가
            if 0 <= next_row < I and 0 <= next_col < I and graph[next_row][next_col] == 0:
                graph[next_row][next_col] = graph[r][c] + 1
                queue.append((next_row, next_col))


for _ in range(T):
    I = int(input())
    chess_board = [[0] * (I + 1) for _ in range(I + 1)]

    row, column = map(int, input().split())
    target_row, target_column = map(int, input().split())
    result = BFS(chess_board, (row, column))
    print(result)

출처: [SWEA] 최빈수 구하기

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

import sys

input = sys.stdin.readline

T = int(input())

for _ in range(T):
    test_case = int(input())
    score_list = list(map(int, input().split()))
    score_list.sort(reverse=True)
    students = {}
    for i in range(101):
        students[i] = 0
    for score in score_list:
        students[score] += 1
    max_value = max(students.values())
    result=0
    for key, value in students.items():
        if value == max_value:
            result = key
    print("#{0} {1}".format(test_case, result))
    # print(max(students.values()))

출처: [백준] 1158번 요세푸스 문제

문제

요세푸스 문제는 다음과 같다.

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.

N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000)

출력

예제와 같이 요세푸스 순열을 출력한다.

예제 입력 1

1

7 3

예제 출력 1

1

<3, 6, 2, 7, 5, 1, 4>

출처

• 문제를 만든 사람: author5

알고리즘 분류

• 자료 구조
• 큐

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

import sys
from collections import deque

input = sys.stdin.readline
N, K = map(int, input().split())

queue = deque([i for i in range(1, N + 1)])

print('<', end='')
while queue:
    for _ in range(K - 1):
        queue.append(queue[0])
        queue.popleft()
    print(queue.popleft(), end="")
    if queue:
        print(',', end=" ")
print('>')

출처: [백준] 2309번 일곱 난쟁이

문제

왕비를 피해 일곱 난쟁이들과 함께 평화롭게 생활하고 있던 백설공주에게 위기가 찾아왔다. 일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉 명이었던 것이다.

아홉 명의 난쟁이는 모두 자신이 “백설 공주와 일곱 난쟁이”의 주인공이라고 주장했다. 뛰어난 수학적 직관력을 가지고 있던 백설공주는, 다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈다.

아홉 난쟁이의 키가 주어졌을 때, 백설공주를 도와 일곱 난쟁이를 찾는 프로그램을 작성하시오.

입력

아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다.

출력

일곱 난쟁이의 키를 오름차순으로 출력한다. 일곱 난쟁이를 찾을 수 없는 경우는 없다.

예제 입력 1

1
2
3
4
5
6
7
8
9

20
7
23
19
10
15
25
8
13

예제 출력 1

1
2
3
4
5
6
7

7
8
10
13
19
20
23

출처

• Olympiad > 한국정보올림피아드 > 한국정보올림피아드시․도지역본선 > 지역본선 2004 > 초등부 1번
  • 어색한 표현을 찾은 사람: upple1

알고리즘 분류

• 브루트포스 알고리즘

소스코드1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

import sys
from itertools import combinations

input = sys.stdin.readline

dwarfs = [int(input()) for _ in range(9)]
dwarfs.sort()

nPr = combinations(dwarfs, 7)

temp = []
for case in list(nPr):
    if sum(case) == 100:
        temp = case
        break
for x in temp:
    print(x)

소스코드2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

import sys

input = sys.stdin.readline

dwarfs = [int(input()) for _ in range(9)]
dwarfs.sort()

height_sum = sum(dwarfs)
delete_element1 = 0
delete_element2 = 0

for i in range(9):
    for j in range(i + 1, 9):
        if height_sum - (dwarfs[i] + dwarfs[j]) == 100:
            delete_element1 = dwarfs[i]
            delete_element2 = dwarfs[j]
            break

for dwarf in dwarfs:
    if dwarf == delete_element1 or dwarf == delete_element2:
        continue
    else:
        print(dwarf)

출처: [백준] 12018번 Yonsei TOTO

문제

연세대학교 수강신청이 얼마 전부터 바뀌어, 마일리지 제도로 바뀌었다. 이 제도는 각각의 학생들에게 마일리지를 주어 듣고 싶은 과목에 마일리지를 과목당 1~36을 분배한다. 그리고 모두 분배가 끝이 나면 과목에 대해서 마일리지를 많이 투자한 순으로 그 과목의 수강인원만큼 신청되는 방식이다.

성준이는 연세대학교 재학 중인 학생이다. 성준이는 저번 수강신청에서 실패하여 휴학을 했기 때문에 이번 수강신청만은 필사적으로 성공하려고 한다. 그래서 성준이는 학교 홈페이지를 뚫어버렸다.

그 덕분에 다른 사람들이 신청한 마일리지를 볼 수 있게 되었다. 성준이는 주어진 마일리지로 최대한 많은 과목을 신청하고 싶어 한다. (내가 마일리지를 넣고 이후에 과목을 신청하는 사람은 없다) 마일리지는 한 과목에 1에서 36까지 넣을 수 있다.

입력

첫째 줄에는 과목 수 n (1 ≤ n ≤ 100)과 주어진 마일리지 m (1 ≤ m ≤ 100)이 주어진다. 각 과목마다 2줄의 입력이 주어지는데 첫째 줄에는 각 과목에 신청한 사람 수 Pi과 과목의 수강인원 Li이 주어지고 그 다음 줄에는 각 사람이 마일리지를 얼마나 넣었는지 주어진다. (1 ≤ Pi ≤100, 1 ≤ Li ≤ 100)

(단 마일리지가 같다면 성준이에게 우선순위가 주어진다고 하자.)

출력

첫째 줄에 주어진 마일리지로 최대로 들을 수 있는 과목 개수를 출력한다.

예제 입력 1

1
2
3
4
5
6
7
8
9
10
11

5 76
5 4 
36 25 1 36 36
4 4
30 24 25 20
6 4
36 36 36 36 36 36
2 4
3 7
5 4
27 15 26 8 14

예제 출력 1

1

4

출처

• • University > 연세대학교 > 2016 연세대 컴퓨터과학과 프로그래밍 경진대회 A번
    • 문제를 만든 사람: zych1751

알고리즘 분류

• 자료 구조
• 그리디 알고리즘
• 정렬
• 우선순위 큐

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

import sys
import heapq

input = sys.stdin.readline

N, M = map(int, input().split())
answer = 0
sugang = []

for _ in range(N):
    P, L = map(int, input().split())
    mileages = list(map(int, input().split()))
    heapq.heapify(mileages)

    available = L - P
    if available > 0:
        heapq.heappush(sugang, 1)
    else:
        for i in range(abs(available)):
            heapq.heappop(mileages)
        heapq.heappush(sugang, heapq.heappop(mileages))

count = 0
while sugang:
    sugang_mileage = heapq.heappop(sugang)
    if M - sugang_mileage >= 0:
        M -= sugang_mileage
        count += 1
    else:
        break
print(count)

출처: [백준] 15903번 카드 합체 놀이

문제

석환이는 아기다. 아기 석환이는 자연수가 쓰여져있는 카드를 갖고 다양한 놀이를 하며 노는 것을 좋아한다. 오늘 아기 석환이는 무슨 놀이를 하고 있을까? 바로 카드 합체 놀이이다!

아기 석환이는 자연수가 쓰여진 카드를 n장 갖고 있다. 처음에 i번 카드엔 ai가 쓰여있다. 카드 합체 놀이는 이 카드들을 합체하며 노는 놀이이다. 카드 합체는 다음과 같은 과정으로 이루어진다.

1. x번 카드와 y번 카드를 골라 그 두 장에 쓰여진 수를 더한 값을 계산한다. (x ≠ y)
2. 계산한 값을 x번 카드와 y번 카드 두 장 모두에 덮어 쓴다.

이 카드 합체를 총 m번 하면 놀이가 끝난다. m번의 합체를 모두 끝낸 뒤, n장의 카드에 쓰여있는 수를 모두 더한 값이 이 놀이의 점수가 된다. 이 점수를 가장 작게 만드는 것이 놀이의 목표이다.

아기 석환이는 수학을 좋아하긴 하지만, 아직 아기이기 때문에 점수를 얼마나 작게 만들 수 있는지를 알 수는 없었다(어른 석환이는 당연히 쉽게 알 수 있다). 그래서 문제 해결 능력이 뛰어난 여러분에게 도움을 요청했다. 만들 수 있는 가장 작은 점수를 계산하는 프로그램을 만들어보자.

입력

첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다.

두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1, a2, …, an이 공백으로 구분되어 주어진다. (1 ≤ ai ≤ 1,000,000)

출력

첫 번째 줄에 만들 수 있는 가장 작은 점수를 출력한다.

예제 입력 1

1
2

3 1
3 2 6

예제 출력 1

1

16

예제 입력 2

1
2

4 2
4 2 3 1

예제 출력 2

1

19

출처

• University > 전국 대학생 프로그래밍 대회 동아리 연합 여름 대회 > UCPC 2018 예선 B번
  • 문제를 만든 사람: haden

알고리즘 분류

• 자료 구조
• 그리디 알고리즘
• 우선순위 큐

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

import sys
import heapq

input = sys.stdin.readline

N, M = map(int, input().split())
card_list = list(map(int, input().split()))

heapq.heapify(card_list)  # card_list를 heap으로 변환

for _ in range(M):
    x, y = heapq.heappop(card_list), heapq.heappop(card_list)
    for _ in range(2):
        heapq.heappush(card_list, x + y)


print(sum(card_list))

출처: [코딩테스트 연습] 디스크 컨트롤러

문제

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.

1

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.

제한

• scoville의 길이는 2 이상 1,000,000 이하입니다.
• K는 0 이상 1,000,000,000 이하입니다.
• scoville의 원소는 각각 0 이상 1,000,000 이하입니다.
• 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.

입출력

입출력 예 1

1. 스코빌 지수가 1인 음식과 2인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
   새로운 음식의 스코빌 지수 = 1 + (2 * 2) = 5
   가진 음식의 스코빌 지수 = [5, 3, 9, 10, 12]
2. 스코빌 지수가 3인 음식과 5인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
   새로운 음식의 스코빌 지수 = 3 + (5 * 2) = 13
   가진 음식의 스코빌 지수 = [13, 9, 10, 12]

모든 음식의 스코빌 지수가 7 이상이 되었고 이때 섞은 횟수는 2회입니다.

풀이

• scoville리스트를 heaq구조로 바꿔주고, 조건에 맞게 두번의 heappop..
• 위 계산을 다시 scoville에 넣어주고 answer카운트 증가–> K 이상될때까지
  K이상이 될 수 없으면 return -1

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

import heapq


def solution(scoville, K):
    answer = 0
    # heap = []
    # for num in scoville:
    #     heapq.heappush(heap, num)
    heapq.heapify(scoville)

    while scoville[0] < K:
        mix = heapq.heappop(scoville) + (heapq.heappop(scoville) * 2)
        heapq.heappush(scoville, mix)
        answer += 1
        if len(scoville) == 1 and scoville[0] < K:
            return -1
    return answer


# print(solution([1, 2, 3, 9, 10, 12], 7))  # 2

출처: [코딩테스트 연습] 디스크 컨트롤러

문제

하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다.

예를들어

1
2
3

- 0ms 시점에 3ms가 소요되는 A작업 요청
- 1ms 시점에 9ms가 소요되는 B작업 요청
- 2ms 시점에 6ms가 소요되는 C작업 요청

와 같은 요청이 들어왔습니다. 이를 그림으로 표현하면 아래와 같습니다.

한 번에 하나의 요청만을 수행할 수 있기 때문에 각각의 작업을 요청받은 순서대로 처리하면 다음과 같이 처리 됩니다.

1
2
3

- A: 3ms 시점에 작업 완료 (요청에서 종료까지 : 3ms)
- B: 1ms부터 대기하다가, 3ms 시점에 작업을 시작해서 12ms 시점에 작업 완료(요청에서 종료까지 : 11ms)
- C: 2ms부터 대기하다가, 12ms 시점에 작업을 시작해서 18ms 시점에 작업 완료(요청에서 종료까지 : 16ms)

이 때 각 작업의 요청부터 종료까지 걸린 시간의 평균은 10ms(= (3 + 11 + 16) / 3)가 됩니다.

하지만 A → C → B 순서대로 처리하면

1
2
3

- A: 3ms 시점에 작업 완료(요청에서 종료까지 : 3ms)
- C: 2ms부터 대기하다가, 3ms 시점에 작업을 시작해서 9ms 시점에 작업 완료(요청에서 종료까지 : 7ms)
- B: 1ms부터 대기하다가, 9ms 시점에 작업을 시작해서 18ms 시점에 작업 완료(요청에서 종료까지 : 17ms)

이렇게 A → C → B의 순서로 처리하면 각 작업의 요청부터 종료까지 걸린 시간의 평균은 9ms(= (3 + 7 + 17) / 3)가 됩니다.

각 작업에 대해 [작업이 요청되는 시점, 작업의 소요시간]을 담은 2차원 배열 jobs가 매개변수로 주어질 때, 작업의 요청부터 종료까지 걸린 시간의 평균을 가장 줄이는 방법으로 처리하면 평균이 얼마가 되는지 return 하도록 solution 함수를 작성해주세요. (단, 소수점 이하의 수는 버립니다)

제한

• jobs의 길이는 1 이상 500 이하입니다.
• jobs의 각 행은 하나의 작업에 대한 [작업이 요청되는 시점, 작업의 소요시간] 입니다.
• 각 작업에 대해 작업이 요청되는 시간은 0 이상 1,000 이하입니다.
• 각 작업에 대해 작업의 소요시간은 1 이상 1,000 이하입니다.
• 하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리합니다.

입출력

입출력 예 1

문제에 주어진 예와 같습니다.

• 0ms 시점에 3ms 걸리는 작업 요청이 들어옵니다.
• 1ms 시점에 9ms 걸리는 작업 요청이 들어옵니다.
• 2ms 시점에 6ms 걸리는 작업 요청이 들어옵니다.

풀이

• 우선순위 큐를 이용해서…
• 현재 시점에서 처리할 수 있는 작업들을 힙에 넣고, 하나를 뽑아 현재 시점과 총 대기시간을 구해주는 것을 모든 작업을 처리할 때까지 반복한다.
  힙에 push를 할 때는 작업의 소요 시간 기준으로 최소힙이 만들어져야 하기 때문에 jobs의 요소를 그대로 넣지 않고 [작업의 소요 시간, 작업이 요청되는 시점]으로 요소의 앞 뒤를 바꿔서 넣어준다.현재 시점에서 처리할 수 있는 작업인지를 판별하는 조건은 작업의 요청 시간이 바로 이전에 완료한 작업의 시작 시간(start)보다 크고 현재 시점(now)보다 작거나 같아야 한다.
  만약 현재 처리할 수 있는 작업이 없다면, 남아 있는 작업들의 요청 시간이 아직 오지 않은 것이기 때문에 현재 시점(now)을 하나 올려준다. 출처

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

import heapq


def solution(jobs):
    answer, now, i = 0, 0, 0
    start = -1
    heap = []

    while i < len(jobs):
        for j in jobs:
            if start < j[0] <= now:
                heapq.heappush(heap, [j[1], j[0]])
        if len(heap) > 0:
            current = heapq.heappop(heap)
            start = now
            now += current[0]
            answer += (now - current[1])
            i += 1
        else:
            now += 1
    return int(answer / len(jobs))


# print(solution([[0, 3], [1, 9], [2, 6]]))  # 9

출처: [백준] 11725번 트리의 부모 찾기

문제

루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.

출력

첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.

예제 입력 1

1
2
3
4
5
6
7

7
1 6
6 3
3 5
4 1
2 4
4 7

예제 출력 1

1
2
3
4
5
6

4
6
1
3
1
4

예제 입력 2

1
2
3
4
5
6
7
8
9
10
11
12

12
1 2
1 3
2 4
3 5
3 6
4 7
4 8
5 9
5 10
6 11
6 12

예제 출력 2

1
2
3
4
5
6
7
8
9
10
11

1
1
2
3
3
4
4
5
5
6
6

출처

• 문제를 만든 사람: baekjoon
• 잘못된 조건을 찾은 사람: jh05013

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 트리
• 너비 우선 탐색
• 깊이 우선 탐색

풀이

소스코드_DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

N = int(input())

trees = {}
for i in range(N):
    trees[i + 1] = set()

for i in range(N - 1):
    a, b = map(int, input().split())
    trees[a].add(b)
    trees[b].add(a)

parents = [False] * (N + 1)


def dfs(graph, v, visited):
    for i in graph[v]:
        if not visited[i]:
            visited[i] = v
            dfs(graph, i, visited)


dfs(trees, 1, parents)
for i in range(2, N + 1):
    print(parents[i])