관리자
글쓰기 / 관리자

백준) 1005_ACM Craft

2023. 5. 13. 12:57· Algorithm/BOJ
728x90
반응형

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

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
    
    static int N, M;
    static int[] seq;
    static int[] value;
    static int[] dp;
    static ArrayList<ArrayList<Integer>> grapgh;
    static StringBuilder sb = new StringBuilder();
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int T = Integer.parseInt(br.readLine());
        while(T --> 0) {
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
            seq = new int[N + 1];
            value = new int[N + 1];
            dp = new int[N + 1];
            grapgh = new ArrayList<>();
            
            for (int i = 0; i < N + 1; i++) {
                grapgh.add(new ArrayList<>());
            }
            
            st = new StringTokenizer(br.readLine());
            for (int i = 1; i < N + 1; i++) {
                value[i] = Integer.parseInt(st.nextToken());
            }
            while(M --> 0) {
                st = new StringTokenizer(br.readLine());
                int u = Integer.parseInt(st.nextToken());
                int v = Integer.parseInt(st.nextToken());
                seq[v]++;
                grapgh.get(u).add(v);
            }
            int destination = Integer.parseInt(br.readLine());
            sb.append(topologicalSort(destination)).append("\n");
        }
        System.out.println(sb.toString());
    }
    
    static int topologicalSort(int destination) {
        Queue<Integer> q = new LinkedList<>();
        for (int i = 1; i < seq.length; i++) {
            if(seq[i] == 0) {
                q.offer(i);
                dp[i] = value[i];
            }
        }
        while (!q.isEmpty()) {
            int cur = q.poll();
            
            if (seq[destination] == 0) {
                break;
            }
            
            for(int next : grapgh.get(cur)) {
                seq[next]--;
                dp[next] = Math.max(dp[next], value[next] + dp[cur]);
                if(seq[next] == 0) {
                    q.offer(next);
                }
            }
        }
        return dp[destination];
    }
}
 
Colored by Color Scripter
cs
728x90
저작자표시 비영리 변경금지 (새창열림)

'Algorithm > BOJ' 카테고리의 다른 글

백준) 1074_Z  (0) 2023.05.16
백준) 11003_최솟값 찾기  (2) 2023.05.14
백준) 21276_계보 복원가 호석  (2) 2023.05.13
백준) 1766_문제집  (1) 2023.05.13
백준) 14676_영우는 사기꾼?  (2) 2023.05.13
'Algorithm/BOJ' 카테고리의 다른 글
  • 백준) 11003_최솟값 찾기
  • 백준) 21276_계보 복원가 호석
  • 백준) 1766_문제집
  • 백준) 14676_영우는 사기꾼?
Junxtar
Junxtar
Git: https://github.com/junxtar
반응형
Junxtar
Junxtar의 개발일지
Junxtar
전체
오늘
어제
  • 분류 전체보기
    • Spring
    • MacBook
      • 화면캡쳐
      • 매직마우스
    • Java
      • 1. 자바 개발도구(JDK)설치하기
      • 2. 변수
      • 3. 포맷팅
      • 4. 화면 입력받기
      • 5. 연산자
      • Do it! 자료구조와 함께 배우는 알고리즘
    • Python
      • Tkinter 패키지
      • Turtle 모듈
      • Pygame 패키지
    • Algorithm
      • 0. 알고리즘 소개
      • 1. 학생이름 저장 및 검색
      • 2. 피보나치 수열
      • 3. 빈도수 구하기
      • 4. 10진수를 2진수로 바꾸기
      • 5. 대문자를 소문자로, 소문자를 대문자로
      • 6. 최대공약수 구하기
      • 7. 최소공배수 구하기
      • 8. 소수판별하기
      • 9. 팩토리얼 구하기
      • 10. 각 자릿수 더하기
      • 11. 숫자 사각형(1)
      • 12. 숫자 사각형(2)
      • 13. 숫자 사각형(3)
      • 14. 숫자 사각형(4)
      • 15. 윤년 구하기
      • 16. 구구단 만들기
      • 17. 별찍기(1)
      • 18. 별찍기(2)
      • 19. 별찍기(3)
      • 20. 최댓값, 최솟값 구하기
      • 21. 가위바위보 게임
      • BOJ
    • Network
      • 쉽게 배우는 데이터 통신과 컴퓨터 네트워크(개정판..
    • 정보처리기사
      • 객체지향 개발 5대 원리: SOLID
      • 애플레케이션 테스트
    • Vue.js
    • Dart
      • Dart 언어에 대해 알아보기
    • DataStructure
    • 회고

블로그 메뉴

  • 홈
  • 태그
  • 방명록
  • 글쓰기
  • 관리하기

공지사항

인기 글

태그

  • 개발 관리 도구
  • 백준
  • entity 자동화
  • BFS
  • 골드3
  • 알고리즘
  • 코딩부트캠프현실
  • 브룩스의 법칙
  • 데이터 통신
  • 컴퓨터 네트워크
  • 테스팅은 정황의존
  • 동적 프로그래밍
  • 계보 복원가 호석
  • 영우는 사기꾼?
  • 연습문제
  • 골드
  • 네트워크
  • 객체 지향 5대원리
  • 객체지향 관점
  • 골드2
  • 개정판
  • jpa 현대화
  • Graddle
  • 쉽게 배우는 데이터 통신과 컴퓨터 네트워크 연습문제
  • 그래프 이론
  • 살충제 페러독스
  • javaparser
  • 위상정렬
  • 스파르타내일배움캠프
  • 쉽게 배우는 데이터 통신과 컴퓨터 네트워크 연습문제 13장

최근 댓글

최근 글

250x250
hELLO · Designed By 정상우.v4.2.1
Junxtar
백준) 1005_ACM Craft
상단으로

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

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

블로그 게시글

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

모든 영역

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

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