[JAVA] 백준 32197 - 절연 구간 최소화

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

정점 A, B를 포함한 N개의 정점이 주어질 때, 간선의 상태 (직류 ==0, 교류 ==1)이 교차되는 -> 절연이 발생하는 횟수가 최소가 되는 경로의 가중치를 구하는 문제이다.

 

첫 노드의 경우는 교류/직류 구분이 없으므로 count하지 않고, 그 외의 경우에는 노드가 현재 가지고 있는 상태와 간선의 상태를 비교해 절연이 발생할 경우 가중치를 +1 해줬다. 

 

절연이 발생하지 않는 간선을 뽑을 경우의 부등호 조건을 잘못 넣어서 한참 고민했다.

ㅠㅠ

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] info = getArray(br.readLine());
        int nodeCount = info[0];
        int roadCount = info[1];
        List<List<P32197>> list = new ArrayList<>();
        for (int i = 0; i <= nodeCount; i++) {
            list.add(new ArrayList<>());
        }
        for (int i = 0; i < roadCount; i++) {
            int[] road = getArray(br.readLine());
            list.get(road[0]).add(new P32197(road[1], road[2]));
            list.get(road[1]).add(new P32197(road[0], road[2]));
        }
        int[] dist = new int[nodeCount + 1];
        info = getArray(br.readLine());
        int startNode = info[0];
        int endNode = info[1];
        Arrays.fill(dist,Integer.MAX_VALUE);
        dijkstra(dist, startNode, list);
        System.out.println(dist[endNode]);
    }

    static void dijkstra(int[] dist, int startNode, List<List<P32197>> list) {
        PriorityQueue<P32197> pq = new PriorityQueue<>();
        dist[startNode] = 0;
        pq.offer(new P32197(startNode));
        boolean[] visited = new boolean[dist.length];
        while (!pq.isEmpty()) {
            P32197 poll = pq.poll();
            int value = poll.to;
            int weight = poll.weight;
            if(visited[value]) continue;
            visited[value] = true;
            List<P32197> vList = list.get(value);
            for (int i = 0; i < vList.size(); i++) {
                P32197 road = vList.get(i);
                int to = road.to;
                int cost = road.weight; //교류/ 직류 여부
                boolean flag = cost == 1; //직류 = false, 교류 = true;
                P32197 offer = new P32197(to);
                if (value == startNode) {//첫 노드는 교류/직류 구분이 없으므로 to까지 이동할때 절연카운트가 증가하지 않음
                    dist[to] = 0;
                } else {
                    boolean mFlag = poll.onOff; //뽑은 노드가 현재 교류 선로 달리는 중 = true , 직류 선로 달리는 중 = false;
                    if(flag!=mFlag){ //절연이면
                        if(dist[to]>dist[value]){//이미 더 적게 절연하는 조건으로 도달한 경우는 제외
                            dist[to] = dist[value] + 1; //이전 카운트 +1
                        } else continue;
                    }else{ //연결
                        if(dist[to]>=dist[value]) {//이미 더 적게 절연하는 조건으로 도달한 경우는 제외
                            dist[to] = dist[value]; //이전 weight 사용
                        } else continue;
                    }
                }
                offer.weight = dist[to];
                offer.onOff = flag;
                pq.offer(offer);
            }
        }
    }

    static int par(String s) {
        return Integer.parseInt(s);
    }

    static int[] getArray(String s) {
        return Arrays.stream(s.split(" ")).mapToInt(Integer::parseInt).toArray();
    }
}

class P32197 implements Comparable<P32197> {
    int to;
    boolean onOff = false;
    int weight = 0; //절연 횟수

    P32197(int t) {
        this.to = t;
    }

    P32197(int t, int weight) {
        this.to = t;
        this.weight = weight;
    }

    @Override
    public int compareTo(P32197 o) {
        return this.weight - o.weight;
    }
}