[백준 알고리즘] 17270번: 연예인은 힘들어 (JAVA)

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

 

코드

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

public class prac {
	public static int V, M, INF;
	public static int[] min_dis;
	public static ArrayList<ArrayList<Node>> arr = new ArrayList<ArrayList<Node>>();

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		st = new StringTokenizer(br.readLine());
		V = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		INF = 1000 * 10000 + 1;

		for (int i = 0; i < V + 1; i++) {
			arr.add(new ArrayList<>());
		}

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

			arr.get(a).add(new Node(b, c));
			arr.get(b).add(new Node(a, c));
		}

		st = new StringTokenizer(br.readLine());
		int J = Integer.parseInt(st.nextToken());
		int S = Integer.parseInt(st.nextToken());

		int[] first = dijkstra(J);
		int[] second = dijkstra(S);

		PriorityQueue<Pos> positionQueue = new PriorityQueue<Pos>();
		int min_v = Integer.MAX_VALUE;

		for (int i = 1; i <= V; i++) {
			if (i == J || i == S)
				continue;
			min_v = Math.min(min_v, first[i] + second[i]);
		}

		// 최솟값이 안되는건 애초에 다 걸러져야 함. 
		// 조건 순서대로 답을 구해줘야 함.
		for (int i = 1; i <= V; i++) {
			if (i == J || i == S)
				continue;
			if (first[i] + second[i] > min_v)
				continue;
			if (first[i] > second[i])
				continue;
			positionQueue.offer(new Pos(first[i], i));
		}

		if (positionQueue.isEmpty())
			System.out.println(-1);
		else
			System.out.println(positionQueue.peek().num);

	}

	public static int[] dijkstra(int start) {
		PriorityQueue<Node> pq = new PriorityQueue<Node>((o1, o2) -> o1.cost - o2.cost);
		min_dis = new int[V + 1];
		Arrays.fill(min_dis, INF);
		min_dis[start] = 0;
		pq.offer(new Node(start, 0));

		while (!pq.isEmpty()) {
			Node cur = pq.poll();

			if (min_dis[cur.node] < cur.cost)
				continue;

			for (Node next : arr.get(cur.node)) {
				if (min_dis[next.node] > cur.cost + next.cost) {
					min_dis[next.node] = cur.cost + next.cost;
					pq.offer(new Node(next.node, cur.cost + next.cost));
				}
			}
		}
		return min_dis;
	}
}

class Node {
	int node;
	int cost;

	public Node(int node, int cost) {
		this.node = node;
		this.cost = cost;
	}
}

class Pos implements Comparable<Pos> {
	int time;
	int num;

	public Pos(int time, int num) {
		this.time = time;
		this.num = num;
	}

	@Override
	public int compareTo(Pos o) {
		if (this.time == o.time) {
			return this.num - o.num;
		}
		return this.time - o.time;
	}
}

 

 

풀이

• 분명히 제대로 구현한거 같은데 "틀렸습니다"를 8%에서 받으셨으리라 생각합니다. 저도 그랬습니다 ! 
• 그 이유는 문제에 주어진 조건을 하나하나 따져가며 답을 추려나가야 하기 때문입니다.
• 제 원래 코드는 다음과 같았습니다

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

public class Main {
	public static int V, M, INF;
	public static int[] min_dis;
	public static ArrayList<ArrayList<Node>> arr = new ArrayList<ArrayList<Node>>();

	public static void main(String[] args) throws Exception {

		int[] first = dijkstra(J);
		int[] second = dijkstra(S);
		PriorityQueue<Pos> positionQueue = new PriorityQueue<Pos>();

		for (int i = 1; i <= V; i++) {
			if (first[i] == INF || second[i] == INF || i == J || i == S || first[i] > second[i])
				continue;
			positionQueue.offer(new Pos(first[i] + second[i], first[i], i));
		}

		if (positionQueue.isEmpty())
			System.out.println(-1);
		else
			System.out.println(positionQueue.peek().num);
	}
}

class Pos implements Comparable<Pos> {
	int sum;
	int time;
	int num;

	public Pos(int sum, int time, int num) {
		this.sum = sum;
		this.time = time;
		this.num = num;
	}

	@Override
	public int compareTo(Pos o) {
		if (this.sum == o.sum) {
			if (this.time == o.time) {
				return this.num - o.num;
			}
			return this.time - o.time;
		}
		return this.sum - o.sum;
	}
}

 

• 이처럼 OR 연산자를 사용해 한번에 선택될 수 있는 값들을 구해주고, 우선순위 큐에 넣어서 정렬한 뒤, peek값을 출력하려고 했습니다.
• 하지만 문제에서는 조건의 순서에 따라 애초에 최단거리의 합이 최소가 되지 않는 값들은 다 제거해준 뒤, 다음 조건으로 넘어가야합니다.
• 이 부분만 잘 고려하시면 문제는 다익스트라를 사용하여 쉽게 해결하실 수 있으리라 생각합니다. 

반례

4 4
1 2 2
1 3 2
2 4 1
3 4 2
1 4

답: -1