백준 10282번(JAVA)

기본적인 다익스트라 문제이지만 원하는 값은 다르다.

정점의 개수가 주어지고 출발점에서 시작해서 도달 할 수 있는정점은 몇개인지(시작점 포함),

그리고 도달 할 수있는 정점중 가장 거리가 먼것은 몇인지 출력하면된다.

간단하게 일반적인 다익스트라를 실시한다.

일반적인 다익스트라에 관한 문제는 아래에 링크를 걸어두겠다.

2021.04.24 - [백준 문제풀이(JAVA)/그래프] - 백준 1916번(JAVA)

백준 1916번(JAVA)

단순하게 시작점에서 해당 정점까지의 거리를 나타내는 dis배열을 한 번 쭉 for문을 이용해 훑어준다.

만약 도달할 수 있는 정점이라면 Integer.MAX_VALUE가 아닐 것이므로 갯수를 ++해주고 max값과 비교하여 계속 더 크면 max값을 갱신한다.

소스코드

import java.util.*;
import java.io.*;
class Node implements Comparable<Node>
{
	int vertex;
	int weight;
	public Node(int vertex,int weight)
	{
		this.vertex=vertex;
		this.weight=weight;
	}
	public int compareTo(Node o)
	{
		return weight-o.weight;
	}//우선순위큐에 넣을 때 간선의 가중치가 작은것이 큰 우선순위를 갖도록 구현
}
public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		int T=Integer.parseInt(br.readLine());
		while(T>0)
		{
			String[] s=br.readLine().split(" ");
			int n=Integer.parseInt(s[0]);
			int d=Integer.parseInt(s[1]);
			int c=Integer.parseInt(s[2]);//시작점
			ArrayList<Node>[] arr=new ArrayList[n+1];
			boolean[] visited=new boolean[n+1];
			int[] dis=new int[n+1];
			Arrays.fill(dis, Integer.MAX_VALUE);
			for(int i=1;i<=n;i++)
			{
				arr[i]=new ArrayList<Node>();
			}
			for(int i=0;i<d;i++)
			{
				s=br.readLine().split(" ");
				int v1=Integer.parseInt(s[0]);
				int v2=Integer.parseInt(s[1]);
				int w=Integer.parseInt(s[2]);
				arr[v2].add(new Node(v1,w));
			}
			PriorityQueue<Node> q=new PriorityQueue<Node>();
			dis[c]=0;
			q.add(new Node(c,0));
			while(!q.isEmpty())
			{
				Node temp=q.poll();
				int v=temp.vertex;
				if(!visited[v])
				{
					for(int i=0;i<arr[v].size();i++)
					{
						int next=arr[v].get(i).vertex;
						if(!visited[next]&&dis[next]>dis[v]+arr[v].get(i).weight)
						{
							dis[next]=dis[v]+arr[v].get(i).weight;
							q.add(new Node(next,dis[next]));
						}
					}
				}
				visited[temp.vertex]=true;
			}//일반적인 다익스트라
			int count=0;//감염된 갯수 세는 용
			int max=0;//c에서 시작해서 도달 할 수 있는 정점중 가장 큰값
			for(int i=1;i<=n;i++)
			{
				if(dis[i]!=Integer.MAX_VALUE)//Integer.MAX_VALUE가 아니라는것은 감염되었다는 뜻이다
				{
					count++;
					max=Math.max(max, dis[i]);
				}
			}
			System.out.println(count+" "+max);
			T--;
		}

	}
}

댓글과 지적은 언제든지 환영입니다~!

글이 마음에 들었다면 왼쪽 이미지를 눌러서 후원 부탁드립니다 ><