[BOJ/백준] 11725 트리의 부모 찾기 (S2)

2024. 7. 23. 18:58· Algorithm PS/Baekjoon Online Judge
목차
  1. 문제
  2. 풀이
  3. Code

문제

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

풀이

해당 문제는 루트 없는 트리에서 각 노드의 부모를 찾아야 한다. 트리의 루트를 1로 정했을 때, 각 노드의 부모를 구하여 출력해야 한다.

 

우선 노드의 개수인 N을 입력받고, 이후 N-1개의 줄에서 두 노드의 연결 정보를 인접 리스트 구조로 입력는다.

그리고 DFS를 시작하여 루트 노드(1)를 방문 처리하고, 연결된 모든 노드를 탐색하면서 각 노드의 부모 노드를 찾는다. DFS는 재귀적으로 호출되며, 현재 노드를 방문 처리하고, 연결된 노드 중 방문하지 않은 노드를 탐색하면서 부모 노드를 설정한다. 모든 노드의 부모를 찾은 후, 2번 노드부터 순서대로 부모 노드를 출력한다. 

Code

import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

    static int N;
    static List<List<Integer>> adjList;  // 인접 리스트
    static boolean[] visited;
    static int[] parents;  // 부모

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());

        adjList = new ArrayList<>();  // 인접 리스트 생성
        for (int i = 0; i <= N; i++) {
            adjList.add(new ArrayList<>());
        }
        visited = new boolean[N + 1];
        parents = new int[N + 1];

        for (int i = 0; i < N - 1; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            adjList.get(a).add(b);
            adjList.get(b).add(a);
        }

        dfs(1); // 루트 노드를 1로 설정하고 시작

        for (int i = 2; i <= N; i++) {
            bw.write(parents[i] + "\n");
        }
        bw.flush(); bw.close();
    }

    private static void dfs(int now) {
        visited[now] = true;  // 현재 노드를 방문 처리

        // 인접 리스트 순회
        for (int node : adjList.get(now)) {
            if (!visited[node]) {  // 방문하지 않은 노드라면?
                parents[node] = now;  // 인접 노드의 부모를 현재 노드로 설정하고
                dfs(node);// 인점 노드 방문
            }
        }
    }
}

728x90

'Algorithm PS > Baekjoon Online Judge' 카테고리의 다른 글

[BOJ/백준] 1074 Z (S1)  (0) 2024.08.10
[BOJ/백준] 1780 종이의 개수 (S2)  (0) 2024.08.09
[BOJ/백준] 2668 숫자고르기 (G5)  (0) 2024.07.23
[BOJ/백준] 24480 알고리즘 수업 - 깊이 우선 탐색 2 (S2)  (0) 2024.07.19
[BOJ/백준] 1012 유기농 배추 (S2)  (1) 2024.07.18
  1. 문제
  2. 풀이
  3. Code
'Algorithm PS/Baekjoon Online Judge' 카테고리의 다른 글
  • [BOJ/백준] 1074 Z (S1)
  • [BOJ/백준] 1780 종이의 개수 (S2)
  • [BOJ/백준] 2668 숫자고르기 (G5)
  • [BOJ/백준] 24480 알고리즘 수업 - 깊이 우선 탐색 2 (S2)
kyung.Kh
kyung.Kh
kyung.Kh
Dev..studynote
kyung.Kh
전체
오늘
어제
07-08 14:26
  • 분류 전체보기 (75)
    • Algorithm PS (32)
      • Baekjoon Online Judge (32)
      • Programmers (0)
    • Computer Science (8)
      • Databse (2)
      • Operating System (1)
      • Computer Network (0)
      • Computer Architecture (0)
      • Algorithm (4)
      • Java & Spring (1)
    • Spring (29)
      • Spring Boot (1)
      • 스프링 핵심 원리 - 기본편(인프런 김영한) (7)
      • Java (1)
      • 자바 ORM 표준 JPA 프로그래밍 (20)
    • Project (2)
      • 문제 & 해결 (2)
    • Book (3)
      • 객체지향의 사실과 오해 (3)
    • 우하한테크코스 (1)
      • precourse (1)

최근 글

인기 글

블로그 메뉴

    태그

    • 재귀
    • 알고리즘
    • BFS
    • 그리디
    • dfs
    • Union-Find
    • Spring
    • 구현
    • 스프링
    • DP
    • 스프링부트
    • 객체지향
    • 스프링 김영한
    • JPA
    • springboot
    • Graph
    • 스프링 기본편
    • 백준
    • 인프런
    • 해시를 사용한 집합과 맵
    hELLO · Designed By 정상우.v4.2.2
    kyung.Kh
    [BOJ/백준] 11725 트리의 부모 찾기 (S2)
    상단으로

    티스토리툴바

    단축키

    내 블로그

    내 블로그 - 관리자 홈 전환
    Q
    Q
    새 글 쓰기
    W
    W

    블로그 게시글

    글 수정 (권한 있는 경우)
    E
    E
    댓글 영역으로 이동
    C
    C

    모든 영역

    이 페이지의 URL 복사
    S
    S
    맨 위로 이동
    T
    T
    티스토리 홈 이동
    H
    H
    단축키 안내
    Shift + /
    ⇧ + /

    * 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.