[DFS/BFS]99클럽 코테 스터디 29일차 TIL + 백준/Silver/6188. Clear Cold Water

[Silver II] Clear Cold Water - 6188 문제 링크

성능 요약 메모리: 55140 KB, 시간: 1464 ms

분류 너비 우선 탐색, 깊이 우선 탐색, 그래프 이론, 그래프 탐색, 트리

제출 일자 2024년 8월 21일 21:38:45

문제 설명

The steamy, sweltering summers of Wisconsin's dairy district stimulate the cows to slake their thirst. Farmer John pipes clear cold water into a set of N (3 <= N <= 99999; N odd) branching pipes conveniently numbered 1..N from a pump located at the barn. As the water flows through the pipes, the summer heat warms it. Bessie wants to find the coldest water so she can enjoy the weather more than any other cow.

She has mapped the entire set of branching pipes and noted that they form a tree with its root at the farm and furthermore that every branch point has exactly two pipes exiting from it. Surprisingly, every pipe is exactly one unit in length; of course, all N pipes connect up in one way or another to the pipe-tree.

Given the map of all the pipe connections, make a list of the distance from the barn for every branching point and endpoint. Bessie will use the list to find the very coldest water.

The endpoint of a pipe, which might enter a branching point or might be a spigot, is named by the pipe's number. The map contains C (1 <= C <= N) connections, each of which specifies three integers: the endpoint E_i (1 <= E_i <= N) of a pipe and two branching pipes B1_i and B2_i (2 <= B1_i <= N; 2 <= B2_i <= N). Pipe number 1 connects to the barn; the distance from its endpoint to the barn is 1.

입력

• Line 1: Two space-separated integers: N and C
• Lines 2..C+1: Line i+1 describes branching point i with three space-separated integers: E_i, B1_i, and B2_i

출력

• Lines 1..N: Line i of the output contains a single integer that is the distance from the barn to the endpoint of pipe i

---

문제 설명

농부 John은 덥고 습한 여름철에 소들이 목을 축일 수 있도록 차가운 물을 농장에 있는 펌프에서 여러 개의 파이프로 보내고 있습니다. 모든 파이프는 1부터 N까지의 번호가 매겨져 있으며, 파이프들은 나무 형태의 구조로 연결되어 있습니다. 이 나무 구조는 루트가 농장에 있으며, 각 가지점에서 정확히 두 개의 파이프가 나뉘어집니다. 또한, 모든 파이프는 길이가 1입니다.

소 Bessie는 가장 차가운 물이 어디에 있는지 찾기 위해, 모든 가지점과 끝점까지의 거리를 알고 싶어합니다. 이때, 파이프 1번은 항상 농장과 연결되어 있으며, 농장과의 거리는 1입니다.

입력

• 첫 번째 줄에 두 정수 N과 C가 주어집니다. (3 ≤ N ≤ 99999; N은 홀수, 1 ≤ C ≤ N)
• 다음 C줄에 걸쳐 각 줄에는 세 정수 E_i, B1_i, B2_i가 주어집니다.
  • E_i는 가지점의 끝점 번호를 나타냅니다.
  • B1_i와 B2_i는 E_i에서 나뉘어지는 두 파이프의 번호를 나타냅니다. (2 ≤ B1_i, B2_i ≤ N)

출력

• 첫 번째 줄부터 N번째 줄까지 각 줄에 i번 파이프의 농장으로부터의 거리를 출력하세요.

예제 입력

5 2
3 5 4
1 2 3

예제 출력

1
2
2
3
3

힌트

예제 입력은 다음과 같은 파이프 구조를 나타냅니다:

                   +------+
                    | Barn |
                    +------+
                       | 1
                       *
                    2 / \ 3
                         *
                      4 / \ 5

• 파이프 1번은 농장과의 거리가 1입니다.
• 파이프 2번과 3번은 파이프 1번에 직접 연결되어 있어, 농장과의 거리는 2입니다.
• 파이프 4번과 5번은 파이프 3번에 연결되어 있어, 농장과의 거리는 3입니다.

<내코드 호소>

from collections import deque


def read_input():
    """입력을 처리하고 트리 구조를 반환하는 함수"""
    # N 파이프 갯수, C 가짓점 갯수
    N, C = map(int, input().split())

    tree = {i: [] for i in range(1, N + 1)}
    for _ in range(C):
        E_i, B1_i, B2_i = map(int, input().split())
        tree[E_i].append(B1_i)
        tree[E_i].append(B2_i)
        # 양방향 연결을 위해 추가
        tree[B1_i].append(E_i)
        tree[B2_i].append(E_i)

    return N, tree

def calculate_distances(N, tree):
    """BFS 또는 DFS를 사용하여 각 파이프의 거리를 계산하는 함수"""
    distances = [-1] * (N + 1) # 인덱스 1부터 사용하기 위해 N + 1크기

    queue = deque([1])
    distances[1] = 1

    while queue:
        current = queue.popleft()

        for neighbor in tree[current]:
            if distances[neighbor] == -1:
                distances[neighbor] = distances[current] + 1
                queue.append(neighbor)

    return distances

def print_distances(distances):
    """계산된 거리를 출력하는 함수"""
    for i in range(1, len(distances)):
        print(distances[i])

if __name__ == "__main__":
    # 1. 입력을 받아 트리 구조 생성
    N, tree = read_input()

    # 2. 각 파이프의 거리를 계산
    distances = calculate_distances(N, tree)

    # 3. 계산된 거리를 출력
    print_distances(distances)

- 백준에서 문제 풀이방법을 알게됨

- DFS는 스택과 set으로 방문체크 / 큐는 BFS라는 것 다시 상기함

- 파이썬 시작방법을 익혀야겠다

<모범사례>

<배운점>