[BOJ] 20168. 골목 대장 호석 - 기능성 (🥇, 백트래킹)

🔗

풀이

출발지에서 목적지로 갈 수 있는 경로는 여러 개가 있을 수 있고, 그 여러 개의 경로 가운데 각 경로가 가지는 골목의 최대 요금값 중 최소를 찾는 문제이다.

우선 목적지까지 도달할 수 있는지 여부를 확인해야 하기 때문에 백트래킹을 사용해 도달할 수 있는 경로들을 판별하고, 해당 경로들의 골목 요금 가운데 최대값을 찾아야 하기 때문에 해당 값에 대해서도 경로를 이동할 때마다 매번 업데이트를 했다(backtracing 변수 maxC). 만일 목적지에 도달한다면 해당 최대값들 가운데 최소값을 구해야 하기 때문에 현재까지 도달한 경로들의 골목 요금들과 비교해서 최소값만을 저장했다.

참고로 한 번 방문했던 골목은 다시 방문할 수 없다. 다시 방문하게 되면 시간 초과가 발생한다.

import java.util.*;
import java.io.*;

public class Main {
    static int N;
    static int B;
    static int C;
    static int answer = 10001;
    static int[][] graph;
    static void backtracing(int cur, int c, int maxC, boolean[] visited) {
        if (c > C) {
            return;
        }
        if (cur == B) {
            answer = Math.min(answer, maxC);
            return;
        }

        for (int i = 1; i <= N; i++) {
            if (graph[cur][i] == 0 || visited[i]) continue;
            visited[i] = true;
            backtracing(i, c + graph[cur][i], Math.max(maxC, graph[cur][i]), visited);
            visited[i] = false;

        }
        return;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int A = Integer.parseInt(st.nextToken());
        B = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());

        graph = new int[N+1][N+1];
        int a; int b; int c;
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
            c = Integer.parseInt(st.nextToken());
            graph[a][b] = c;
            graph[b][a] = c;
        }

        boolean[] visited = new boolean[N+1];
        backtracing(A, 0, 0, visited);

        if (answer == 10001) {
            System.out.println(-1);
        } else {
            System.out.println(answer);
        }

    }
}