글 읽기 - 풀이 방법이 틀린 것 같은데 도움 부탁드려요

isp2490 3년 전 0

아이템의 가격을 구하는 로직을 dfs를 이용해서 구하려고 했습니다

ex)

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

에서 1의 가격을 구하기 위해

4의 가격과 4의 조합가격의 최소값을, 5의 가격과 조합가격의 최소값을 구하고

해당 재료가 조합이 가능할 경우 다시 재료의 가격과 조합가격을 구하는 방식으로 로직을 작성했지만 틀렸습니다ㅜㅜ

접근이 잘못된건지 도움이 필요합니다ㅜㅜ

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int toolCnt = sc.nextInt();
        int makeCnt = sc.nextInt();
        int[][] charge = new int[toolCnt + 1][3];
        boolean[] visit = new boolean[toolCnt + 1];
        for (int i = 1; i <= toolCnt; i++) {
            charge[i][0] = sc.nextInt();
        }
        for (int i = 0; i < makeCnt; i++) {
            int toolNum = sc.nextInt();
            int material1 = sc.nextInt();
            int material2 = sc.nextInt();
            visit[toolNum] = true;
            charge[toolNum][1] = material1;
            charge[toolNum][2] = material2;
        }
        dfs(1, charge, visit);
        System.out.print(charge[1][0] + "");
    }

    private static void dfs(int toolNum, int[][] charge, boolean[] visit) {
        if (!visit[toolNum]) return;
        visit[toolNum] = false;
        if (visit[charge[toolNum][1]]) dfs(charge[toolNum][1], charge, visit);
        if (visit[charge[toolNum][2]]) dfs(charge[toolNum][2], charge, visit);
        charge[toolNum][0] = Math.min(charge[toolNum][0], charge[charge[toolNum][1]][0] + charge[charge[toolNum][2]][0]);
    }
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

풀이 방법이 틀린 것 같은데 도움 부탁드려요

isp2490 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말