백준 - 14938. 서강그라운드

반례를 생각하지 못해서 해결하는데 한 시간이 넘는 시간이 걸려 내용을 정리하고자 한다.

 

14938. 서강그라운드

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

 

 

문제

 

입출력

 

설명

item의 개수와 가중치가 있는 그래프가 주어진다.

한 node에서부터 가중치의 합이 r 이내인 node들의 item의 합을 구하는 문제이다.

 

 

접근

아래 방법으로 풀었다.

1. 각 node마다 거리가 r 이하인 node를 visited true로 변경
2. visited가 true인 node의 item 값을 더함

자꾸 9%에서 틀려서 오래 고민했다가 해결했다.

 

우선순위 큐를 활용해 거리가 짧은 node부터 방문하도록 구현했는데 

visited를 활용해 한 번 접근한 node는 다시 접근하지 않도록 구현한 것이 문제였다.

 

그래프의 입력이

1 2 3

2 3 3

1 3 4

인 경우 

 

1 -> 2 -> 3으로 가면 비용이 6이고

1 -> 3으로 가면 비용이 4인데 

 

우선순위에 따라서 이런 경우 비용이 6인 경로가 우선되었다.

 

이 문제를 해결하니 곧바로 풀이에 성공했다.

 

 

풀이 코드

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

public class Main {

	static int n;
	static int m;
	static int r;
	static int[] items;
	static List<Node>[] graph;

	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());
		m = Integer.parseInt(st.nextToken());
		r = Integer.parseInt(st.nextToken());

		items = new int[n+1];
		graph = new ArrayList[n+1];
		st = new StringTokenizer(br.readLine());
		for (int i = 1; i <= n; i++) {
			items[i] = Integer.parseInt(st.nextToken());
			graph[i] = new ArrayList<>();
		}

		int[][] nodeInfos = new int[r][3];
		for (int i = 0; i < r; i++) {
			st = new StringTokenizer(br.readLine());
			nodeInfos[i][0] = Integer.parseInt(st.nextToken());
			nodeInfos[i][1] = Integer.parseInt(st.nextToken());
			nodeInfos[i][2] = Integer.parseInt(st.nextToken());
		}

		Arrays.sort(nodeInfos, new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				return o1[2] - o2[2];
			}
		});

		for (int i = 0; i < r; i++) {
			graph[nodeInfos[i][0]].add(new Node(nodeInfos[i][1], nodeInfos[i][2]));
			graph[nodeInfos[i][1]].add(new Node(nodeInfos[i][0], nodeInfos[i][2]));
		}

		System.out.print(getAnswer());
	}

	static int getAnswer() {
		int max = 0;
		for (int i = 1; i <= n; i++) {
			max = Math.max(getItems(i), max);	
		}
		return max;
	}

	static int getItems(int start) {
		boolean[] visited = new boolean[n+1];
		visited[start] = true;

		Queue<Movement> pq = new PriorityQueue<>();
		pq.add(new Movement(start, 0));

		while (!pq.isEmpty()) {
			Movement movement = pq.poll();
			for(Node node : graph[movement.currentNode]) {
				if(m < movement.moveLength + node.weight) {
					continue;
				}

				visited[node.to] = true;
				pq.add(new Movement(node.to, movement.moveLength + node.weight));
			}
		}

		int numberOfItems = 0;
		for (int i = 1; i <= n; i++) {
			if(visited[i]) {
				numberOfItems += items[i];
			}
		}
		return numberOfItems;
	}
}

class Movement implements Comparable<Movement> {

	int currentNode;
	int moveLength;	

	Movement(int currentNode, int moveLength) {
		this.currentNode = currentNode;
		this.moveLength = moveLength;
	}

	@Override
	public int compareTo(Movement o) {
		return moveLength - o.moveLength;
	}

}

class Node {

	int to;
	int weight;

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

}

 

 

후기

열심히 해야겠다.