[11657] 타임머신

✔ 타임머신

[백준 11657]

문제 분석하기

시작점 및 다른 노드와 관련된 최단 거리를 구하는 문제이며,

엣지에 해당하는 이동하는 시간이 양수가 아닌 0 또는 음수가 가능하므로 발만-포드 알고리즘을 사용

손으로 풀어보기

1. 엣지 리스트에 엣지 데이터를 저장한 후 거리 배열을 초기화
2. 벨만-포드 알고리즘을 수행
3. 음수 사이클이 존재하면 -1, 존재하지 않으면 거리 배열의 값을 출력
   • 단, 거리 배열의 값이 INF일 경우에는 -1을 출력

슈도코드 작성하기

자료 구조 선언하기(그래프 정보 저장, 최단 거리 저장)
N(노드 개수)
M(엣지 개수)
Edges(엣지 리스트 배열)
거리 배열을 충분히 큰 수로 초기화하기
for(엣지 개수) {
    엣지 리스트 배열에 이 엣지 정보를 저장하기
}
거리 배열에 출발 노드 0으로 초기화하기
for(노드 개수 - 1) {
    for(엣지 개수) {
        현재 엣지 데이터 가져오기
        if(출발 노드가 무한대가 아니며 종료 노드값 > 출발 노드값 + 엣지 가중치) {
            업데이트 수행 → 종료 노드값 = 출발 노드값 + 엣지 가중치
        }
    }
}
for(엣지 개수) {
    현재 엣지 데이터 가져오기
    if(출발 노드가 무한대가 아니며 종료 노드값 > 출발 노드값 + 엣지 가중치) {
        업데이트 가능 → 음수 사이클 존재
    }
}
음수 사이클 미존재 → 거리 배열 출력하기(단, 거리 배열의 값이 무한대일 때 -1 출력)
음수 사이클 존재 → -1 출력하기
Edge {
    start(출발 노드)
    end(종료 노드)
    time(엣지의 가중치)
}

코드 구현하기

/**
 * 11657) 타임머신
 */
public class D059_11657 {
    // 최단 거리 저장
    static long distance[];
    // 그래프 정보 저장
    static bEdge edges[];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        // N(노드 개수)
        int N = Integer.parseInt(st.nextToken());
        // M(엣지 개수)
        int M = Integer.parseInt(st.nextToken());
        // Edges(엣지 리스트 배열)
        edges = new bEdge[M + 1];
        // 거리 배열을 충분히 큰 수로 초기화하기
        distance = new long[N + 1];
        Arrays.fill(distance, Integer.MAX_VALUE);
        // 엣지 리스트 배열에 엣지 정보를 저장하기
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int time = Integer.parseInt(st.nextToken());
            edges[i] = new bEdge(start, end, time);
        }
        // 거리 배열에 출발 노드 0으로 초기화하기
        distance[1] = 0;
        for (int i = 1; i < N; i++) {
            for (int j = 0; j < M; j++) {
                // 현재 엣지 데이터 가져오기
                bEdge edge = edges[j];
                // 출발 노드가 무한대가 아니며 종료 노드값 > 출발 노드값 + 엣지 가중치
                if (distance[edge.start] != Integer.MAX_VALUE
                        && distance[edge.end] > distance[edge.start] + edge.time) {
                    // 업데이트 수행 → 종료 노드값 = 출발 노드값 + 엣지 가중치
                    distance[edge.end] = distance[edge.start] + edge.time;
                }
            }
        }
        // 음수 사이클 확인하기
        boolean myCycle = false;
        for (int i = 0; i < M; i++) {
            // 현재 엣지 데이터 가져오기
            bEdge edge = edges[i];
            // 출발 노드가 무한대가 아니며 종료 노드값 > 출발 노드값 + 엣지 가중치
            if (distance[edge.start] != Integer.MAX_VALUE && distance[edge.end] > distance[edge.start] + edge.time) {
                // 업데이트 가능 → 음수 사이클 존재
                myCycle = true;
            }
        }
        // 음수 사이클 미존재 → 거리 배열 출력하기
        if (!myCycle) {
            for (int i = 2; i <= N; i++) {
                if (distance[i] == Integer.MAX_VALUE)
                    System.out.println("-1");
                else
                    System.out.println(distance[i]);
            }
        }
        // 음수 사이클 존재 → -1 출력하기
        else {
            System.out.println("-1");
        }
    }
}

class bEdge {
    // start(출발 노드)
    int start;
    // end(종료 노드)
    int end;
    // time(엣지의 가중치)
    int time;

    public bEdge(int start, int end, int time) {
        this.start = start;
        this.end = end;
        this.time = time;
    }
}