백준 7040번: 밥 먹기(Java, 그래프, 벨만-포드)

HamJina·2025년 8월 28일

백준

목록 보기

12/17

☑️ 문제

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

✔️관련 알고리즘 개념

벨만-포드

☑️ 문제 분석

우선 문제 조건에서 1번부터 N번까지의 소들이 번호순대로 줄을 설 때 1번소와 N번 소의 최대 거리를 구해야 한다.
예시 입력 1을 분석해보자

소는 1번부터 4번까지 4마리가 있고 서로를 좋아하는 소의 쌍은 2쌍, 서로를 싫어하는 소의 쌍은 1쌍이 있다.
1번, 3번 소는 서로를 좋아하므로 최대 10까지만 떨어져 있을 수 있고
2번, 4번 소도 서로를 좋아하므로 최대 20까지만 떨어져 있을 수 있다.
그리고
2번, 3번 소는 서로를 싫어하므로 최소 3만큼 떨어져 있어야 한다.
최종적으로 1번과 4번의 최대 거리를 구해야 하므로 최대한 소들이 서로 떨어져 있게끔 한다.

위 그림을 보면 2와 4가 최대 20만큼 떨어져 있다. 이제 1과 2가 최대한 멀리 떨어져 있을 수록 1과 4사이의 거리가 최대일 것이다.
또한 1과 3이 최대 2만큼 떨어져 있다. 이제 3과 4가 최대한 멀리 떨어져 있을 수록 1과 4사이의 거리가 최대일 것이다. 예시 입력 1에서는
2와 3의 최소 거리가 나와 있으므로 전자를 이용하여 문제를 풀면된다.
따라서 1과 2사이 최대 거리는 7, 2와 4사이 최대 거리는 20이므로 1과 4사이의 최대거리는 27이다.

위의 과정을 벨만-포드를 적용하여 이해해보자

에지리스트 – (c1, c2, d)순

(1, 3, 10)

(2, 4, 20)

(2, 3, 3)

1번째 업데이트

(1)(1, 3, 10)

1번소의 distance[1] != ∞ => distance[3] = 10으로 업데이트

(2) (2, 4, 20)

2번 소의 distance[2] = ∞ => 업데이트 불가

(3) (2, 3, 3)은 최소 거리이고 우리는 3번 소의 distance[3] = 10 (!= ∞)

라는 것을 이용해서 distance[2] = distance[3] – 10 = 7로 업데이트

여기서

MD배열에서 distance[c2] != ∞이면 distance[c1] = distance[c2] – d로 계산할 수 있다.

ML배열은 일반적인 벨만포드와 같이 계산하면 된다.

2번째 업데이트

(1)(1, 3, 10)

업데이트 진행할 것 없음

(2) (2, 4, 20)

distance[2] != ∞ => distance[4] = distance[2] +20 = 27로 업데이트

(3) (2, 3, 3)

업데이트 진행할 것 없음

최종적으로 한번 더 에지리스트를 순회하여

업데이트 되는 값이 있으면 음수사이클이 존재하는 것과 같으므로 줄을 서는 것이 불가 -> 1을 출력
distance[N] = ∞ -> 2출력
줄서는것이 가능 & distance[N] != ∞ -> distance[N] 출력

☑️ 코드

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

public class Main {
    static int[] distance; // 거리 배열
    static List<Edge> edge = new ArrayList<>(); // 에지 리스트
    static int N;
    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 ML = Integer.parseInt(st.nextToken());
        int MD = Integer.parseInt(st.nextToken());

        distance = new int[N+1];
        Arrays.fill(distance, Integer.MAX_VALUE);

        // ML 입력받기
        for (int i = 0; i < ML; i++) {
            st = new StringTokenizer(br.readLine());
            int c1 = Integer.parseInt(st.nextToken());
            int c2 = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());
            edge.add(new Edge("ML", c1, c2, d));
        }

        // MD 입력받기
        for (int i = 0; i < MD; i++) {
            st = new StringTokenizer(br.readLine());
            int c1 = Integer.parseInt(st.nextToken());
            int c2 = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());
            edge.add(new Edge("MD", c1, c2, d));
        }

         // 시작 노드의 거리 배열 값은 0이다.
        distance[1] = 0;
         // N-1번 벨만-포드를 반복한다.
        for (int i = 0; i < N - 1; i++) {
            for (Edge e : edge) {
                if(e.mode.equals("ML")) {
                    if(distance[e.c1] != Integer.MAX_VALUE && distance[e.c2] > distance[e.c1] + e.d) {
                        distance[e.c2] = distance[e.c1] + e.d;
                    }
                } else if(e.mode.equals("MD")) {
                    if(distance[e.c2] != Integer.MAX_VALUE && distance[e.c1] > distance[e.c2] - e.d) {
                        distance[e.c1] = distance[e.c2] - e.d;
                    }
                }
            }
        }

        boolean imPossible = false;
        for (Edge e : edge) {
            if(e.mode.equals("ML")) {
                if(distance[e.c1] != Integer.MAX_VALUE && distance[e.c2] > distance[e.c1] + e.d) {
                    imPossible = true;
                }
            } else if(e.mode.equals("MD")) {
                if(distance[e.c2] != Integer.MAX_VALUE && distance[e.c1] > distance[e.c2] - e.d) {
                    imPossible = true;
                }
            }
        }

        if(imPossible) System.out.println(-1);
        else if(distance[N] == Integer.MAX_VALUE) System.out.println(-2);
        else System.out.println(distance[N]);
    }

    static class Edge {
         String mode;
         int c1;
         int c2;
         int d;

         Edge(String mode, int c1, int c2, int d) {
             this.mode = mode;
             this.c1 = c1;
             this.c2 = c2;
             this.d = d;
         }
    }

}

☑️ 채점 결과 : 틀림 → 맞음

처음에는 벨만-포드는 최단거리 문제인데 여기는 최대 거리를 구하라고 해서 Integer.MAX_VALUE가 아닌 Integer,MIN_VALUE를 사용해서 틀렸다.

📰

백준 7040번은 "최대 거리"를 직접 구하는 문제가 아닙니다.

실제로는 제약조건을 만족하는 최소 거리를 구하는 문제예요.

제약 조건

ML 도로 (일반 도로)
- c2 - c1 ≤ d 즉, c2는 c1보다 최대 d만큼 멀다. 👉 최단거리 그래프의 "정방향 간선" 제약처럼 동작.
MD 도로 (검문 도로)
- c2 - c1 ≥ d 즉, c1은 c2보다 최소 d만큼 가깝다. 👉 c1 ≤ c2 - d라는 불평등식. 이 역시 "최단거리 제약" 형태.