[파이썬, 자바] 백준 9370 : 미확인도착지 (골드2)

[파이썬, 자바] 백준 9370 : 미확인도착지 (골드2)

• https://www.acmicpc.net/problem/9370

---

풀이

방향성 생각

• state 기반 / 다익스트라 여러 번 사용하기
  • 후자 풀이는 그냥 풀면 되니까...
• 첫 풀이는 state 기반으로 접근
• 힙에다가 (시간,노드,상태)를 넣고 지나야 하는 간선을 지난 경우에 상태값을 변화시켜서 풀이.
• 방문 배열도 2차원으로 V[미방문 / g->h / h->g][노드 수] 이런식으로 방문했는데, 상태가 변하면서 최단거리로 이동하지 않는 문제가 발생.
• 질문게시판에 간선 가중치를 2배로 바꿔주고 특정 간선에만 가중치를 -1로 빼서 다익스트라 사용 시, 후보 노드에 홀수 기록 시 해당 간선을 지났음을 확인하는 아이디어가 있어서 해당 풀이 사용

 

---

파이썬

import heapq as hq
import sys

input = lambda : sys.stdin.readline().rstrip()
INF = float('inf')

for _ in range(int(input())):

    N,M,T = map(int,input().split())
    s,c1,c2 = map(int,input().split())

    G = [[] for _ in range(N+1)]
    for _ in range(M):
        a,b,cost = map(int,input().split())
        G[a].append((b, 2*cost-1 if (a,b) in [(c1,c2),(c2,c1)] else 2*cost))
        G[b].append((a, 2*cost-1 if (a,b) in [(c1,c2),(c2,c1)] else 2*cost))

    target = [int(input()) for _ in range(T)]
    V = [INF]*(N+1)
    V[s] = 0
    heap = [(0,s)]

    while heap:

        t,x = hq.heappop(heap)

        if t > V[x]:
            continue

        for nx,cost in G[x]:

            nt = t+cost
            if nt < V[nx]:
                V[nx] = nt
                hq.heappush(heap,(nt,nx))

    print(*sorted(i for i in target if V[i]%2 == 1))

자바

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

public class Main {
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int test = Integer.parseInt(br.readLine().trim());

        for (int tc = 0; tc < test; tc++) {
            StringTokenizer st = new StringTokenizer(br.readLine().trim());
            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());
            int T = Integer.parseInt(st.nextToken());

            st = new StringTokenizer(br.readLine().trim());
            int s = Integer.parseInt(st.nextToken());
            int c1 = Integer.parseInt(st.nextToken());
            int c2 = Integer.parseInt(st.nextToken());

            ArrayList<ArrayList<int[]>> G = new ArrayList<>();
            for (int i = 0; i <= N; i++) {
                G.add(new ArrayList<>());
            }

            for (int i = 0; i < M; i++) {
                st = new StringTokenizer(br.readLine().trim());
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
                int cost = Integer.parseInt(st.nextToken());

                if ((a == c1 && b == c2) || (a == c2 && b == c1)) {
                    cost = 2 * cost - 1;
                } else {
                    cost = 2 * cost;
                }

                G.get(a).add(new int[] {b, cost});
                G.get(b).add(new int[] {a, cost});
            }

            int[] target = new int[T];
            for (int i = 0; i < T; i++) {
                target[i] = Integer.parseInt(br.readLine().trim());
            }

            // final int INF = Integer.MAX_VALUE;
            final int INF = 1000000000;
            int[] V = new int[N + 1];
            Arrays.fill(V, INF);
            V[s] = 0;

            PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(info -> info[0]));
            pq.offer(new int[] {0, s});

            while (!pq.isEmpty()) {
                int[] info = pq.poll();
                int t = info[0];
                int x = info[1];

                if (t > V[x]) {
                    continue;
                }

                for (int[] next : G.get(x)) {
                    int nx = next[0];
                    int cost = next[1];
                    int nt = t + cost;

                    if (nt < V[nx]) {
                        V[nx] = nt;
                        pq.offer(new int[] {nt, nx});
                    }
                }
            }

            Arrays.sort(target);

            StringBuilder sb = new StringBuilder();
            for (int i : target) {
                if (V[i] % 2 == 1) {
                    sb.append(i).append(" ");
                }
            }
            System.out.println(sb.toString().trim());
        }
    }
}

• 입력 line마다 StringTokenizer 불러주고, 출력은 StringBuilder 사용해서 똑같이 했는데 자꾸 틀렸다해서 한참 찾았다.
• 자료형에서 에러를 많이 겪질 않아서 에러잡기가 힘들다...

---

코멘트

• 아이디어 겟