[백준] 2637 장난감 조립 - Java

2023. 9. 25. 13:00· Algorithm/백준 문제풀이
목차
  1. 문제 출저
  2. 문제 풀이
  3. 소스 코드

 

 

문제 출저

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

 

2637번: 장난감 조립

첫째 줄에는 자연수 N(3 ≤ N ≤ 100)이 주어지는데, 1부터 N-1까지는 기본 부품이나 중간 부품의 번호를 나타내고, N은 완제품의 번호를 나타낸다. 그리고 그 다음 줄에는 자연수 M(3 ≤ M ≤ 100)이 주

www.acmicpc.net

 

 

문제 풀이

장난감의 종류와 각 장난감이 조립되기 위한 부품들을 알려줍니다. 이 때, 부품은 기본 부품과 중간 부품이 있습니다. 기본 부품은 다른 부품 조립에 사용되는 부품으로 다른 부품으로 조립할 수 없는 기본 부품 입니다. 중간 부품은 부품들로 이루어진 부품들입니다. 최종 완제품 N을 조립하는게 기본 부품이 몇 개 필요한지 구하는게 이 문제의 요구사항 입니다. 

 

 

위상 정렬로 풀었습니다. 

클래스 part(int index, int number) 를 생성하여 몇 번째 부품이 몇 개 필요한지 저장했습니다. 

List<part>[] partList 를 선언하여 제품을 만드는데 어떤 부품이 몇 개가 필요한지를 저장했습니다.

int[] need를 선언하여 이 부품이 몇 개의 부품의 가짓수가 필요한지 저장했습니다.

boolean[] basic 을 선언하여 기본 부품을 true로 저장했습니다.

static int[] part 을 선언하여 완제품을 위한 필요한 부품들의 갯수를 저장했습니다. 

 

입력을 받을 때 partList에 저장하고 need의 가짓수를 올립니다.

입력을 다 받고 난 후 partList를 for문으로 순회하면서 사이즈가 0인 부품은 기본 부품이므로 해당 부붐의 basic을 true로 바꿉니다.

Queue<Integer> 를 선언하여 완제품을 N을 넣고 탐색을 진행합니다. 

While을 이용해 que가 빌 때 까지 탐색합니다.

하나를 꺼내 part 부분에 현재 꺼낸 갯수와 필요한 갯수를 곱하여 더합니다.

need에 탐색을 마친 index를 뺍니다. 이 때 need가 0이 되면 다시 que에 넣습니다. (필요한 조건을 충족했으니 탐색 대상이 됨)

이런 식으로 탐색을 반복하여 part를 완성합니다.

basic을 순회하면서 true인 index와 같은 위치인 part를 출력합니다. 

 

 

소스 코드

package baekjoon.backjoon9.day25;

/*
장난감 조립
https://www.acmicpc.net/problem/2637
 */

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class B2637 {

    static int n, m;
    static List<part>[] partList;
    static int[] need; // 필요한 갯수
    static boolean[] basic; // 기본 부품
    static int[] part; // 부품 갯수


    public static void main(String[] args) throws IOException {


        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());
        m = Integer.parseInt(br.readLine());

        partList = new List[n + 1];
        for (int i = 0; i < n + 1; i++) {
            partList[i] = new ArrayList<>();
        }

       need = new int[n+1];

       StringTokenizer st = null;

       for(int i = 0; i < m; i++) {
           st = new StringTokenizer(br.readLine());

           int target = Integer.parseInt(st.nextToken());
           int needIndex = Integer.parseInt(st.nextToken());
           int needNumber = Integer.parseInt(st.nextToken());

           partList[target].add(new part(needIndex, needNumber));

           need[needIndex]++;
       }

       basic = new boolean[n+1];

       for(int i = 1; i < n; i++) {
           if(partList[i].size() == 0) {
               basic[i] = true;
           }
       }

       part = new int[n + 1];
       part[n] = 1;

       Queue<Integer> que = new LinkedList<>();
       que.add(n);


        while (!que.isEmpty()) {
            Integer index = que.poll();

            for(part p : partList[index]) {
                part[p.index] += p.number * part[index];
                need[p.index] -= 1;

                if(need[p.index] == 0) {
                    que.add(p.index);
                }
            }
        }

        StringBuilder sb = new StringBuilder();

        for(int i = 1; i < n+1; i++) {
            if(basic[i]) {
                sb.append(i).append(" ").append(part[i]).append("\n");
            }
        }

        System.out.println(sb);


    }

    public static class part {
        int index;
        int number;

        part(int index, int number) {
            this.index = index;
            this.number = number;
        }
    }





}

 

 

 

  1. 문제 출저
  2. 문제 풀이
  3. 소스 코드
'Algorithm/백준 문제풀이' 카테고리의 다른 글
  • [백준] 6087 레이저 통신 - Java
  • [백준] 2623 음악프로그램 - Java
  • [백준] 16637 괄호 추가하기 - Java
  • [백준] 16564 히오스 프로게이머 - Java
너지살
너지살
너지살
너지살개발자
너지살
전체
오늘
어제
  • 분류 전체보기 (375)
    • 잡식 (2)
      • 티스토리 (2)
    • 개발 일지 (0)
      • OMS 프로젝트 (4)
      • 우테코 6기 프리코스 (1)
    • Git (2)
    • JAVA (15)
      • Java 공부 (6)
      • 자료구조 (4)
      • 도움되는 메모 (4)
    • DevOps (18)
      • AWS (6)
      • Docker (2)
      • Jenkins (1)
      • Nginx (1)
      • Kafka (6)
      • RabbitMQ (2)
    • Spring, Spring Boot (16)
      • Test Code (1)
      • AOP (2)
      • Batch (3)
      • Cache - Redis (5)
      • Cloud Config - 설정 파일 관리 (3)
      • 성능 측정 (1)
      • 예외 처리 (1)
    • BackEnd (1)
      • Spring 공부 (1)
      • Thymeleaft (0)
    • DB (17)
      • JPA (2)
      • DB 공부 (3)
      • DB 포스팅 (4)
      • DB 답장 (1)
      • MySQL (2)
      • Redis (5)
      • MongoDB (0)
    • CS (8)
      • Spring (4)
      • DataBase (3)
      • Java (1)
    • Algorithm (203)
      • 알고리즘 개념 (5)
      • 정렬 알고리즘 (11)
      • 프로그래머스 문제풀이 (18)
      • 백준 문제풀이 (165)
      • 소프티어 문제풀이 (3)
      • 알고리즘 시험 정리 (1)
    • SQL (0)
      • 문법 (1)
      • 프로그래머스 문제풀이 (52)
      • 리트코드 문제풀이 (19)
    • IT (1)
      • IT 공부 (1)
    • 정리 (10)
      • 질문 정리 (10)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • git
  • docker
  • Spring Boot Redis 연결
  • Test code
  • 외판원 순회 문제
  • DP
  • 다이나믹 프로그래밍
  • redis
  • 비트마스킹
  • Union-Find
  • cache
  • JPA
  • DFS
  • 병렬 처리
  • 크루스칼 알고리즘
  • Java 정리
  • 설정
  • dynamic programing
  • Spring Boot
  • Algorithm
  • 투 포인터
  • 알고리즘
  • 두 포인터
  • 최소 신장 트리
  • 질문 정리
  • Bitmast
  • Next permutation
  • 그래프 탐색
  • 소프티어
  • Sorting algorithm
  • 다음 순열 찾기
  • 그래프 이론
  • 자료구조
  • 우선수위큐
  • db
  • Java
  • dynamiceprogramming
  • 분리 집합
  • MST
  • 깊이/너비 우선탐색
  • Spring Batch
  • two pointer
  • 백준
  • 유니온파인드
  • 투포인트
  • 부분탐색
  • 다이나믹프로그래밍
  • 최소 스패닝 트리
  • 데이터베이스
  • 경로표현식

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.2
너지살
[백준] 2637 장난감 조립 - Java
상단으로

티스토리툴바

단축키

내 블로그

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

블로그 게시글

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

모든 영역

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

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