백준 10217번(JAVA) - KCM Travel, 재채점 후 새로운 풀이

분명히 맞았던 문제인데 갑자기 재채점 되면서 시간초과로 틀렸다.

알고보니 어떤 분이 질문게시판에 예시로 어떤 입력을 보여주면서, 이걸로 하면은 대부분의 코드들이 시간초과가 나온다고 질문글을 올렸고(1년전) 그게 최근에 검토가되서 재채점이 된 것이다.

내 기억이 맞다면 이 문제는 꽤 많은 사람들이 맞춰가지고, 다익스트라 분류로 들어가면 상위권에 노출되던 문제였다.

그런데 재채점 후 

저~~ 하위권으로 내려갔을 정도로 재채점 후 많은 분들이 틀렸다

그래서 내 다익스트라를 조금 더 다듬어봤다.

import java.util.*;
import java.io.*;
class Node implements Comparable<Node>
{
	int v;
	int c;
	int d;
	Node(int v,int c,int d)
	{
		this.v=v;
		this.c=c;
		this.d=d;
	}
	public int compareTo(Node o)
	{
		return d-o.d;	
	}
}
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());
		String[] s=br.readLine().split(" ");
		int N=Integer.parseInt(s[0]);
		int M=Integer.parseInt(s[1]);
		int K=Integer.parseInt(s[2]);
		ArrayList<Node>[] arr=new ArrayList[N+1];
		for(int i=1;i<=N;i++)
		{
			arr[i]=new ArrayList<Node>();
		}
		for(int i=0;i<K;i++)
		{
			s=br.readLine().split(" ");
			int u=Integer.parseInt(s[0]);
			int v=Integer.parseInt(s[1]);
			int c=Integer.parseInt(s[2]);//비용
			int d=Integer.parseInt(s[3]);//시간
			arr[u].add(new Node(v,c,d));//양방향이 아니다
		}
		int[][] dis=new int[M+1][N+1];//앞에는 비용, 뒤에는 노드번호, value는 시간
		for(int i=0;i<=M;i++)//다익스트라 기본, 모든 거리를 Max Value로 채워준다
		{
			Arrays.fill(dis[i], Integer.MAX_VALUE);
		}
		dis[0][1]=0;//시작점은 초기화
		PriorityQueue<Node> pq=new PriorityQueue<Node>();
		pq.add(new Node(1,0,0));
		boolean[][] visited=new boolean[M+1][N+1];
		while(!pq.isEmpty())
		{
			Node temp=pq.poll();
			if(visited[temp.c][temp.v])
			{
				continue;
			}
			visited[temp.c][temp.v]=true;
			for(Node next : arr[temp.v])
			{
				if(next.c+temp.c>M)
				{
					continue;
				}
				if(dis[next.c+temp.c][next.v]>temp.d+next.d)
				{
					for(int i=next.c+temp.c;i<=M;i++)
					{
						if(dis[i][next.v]<temp.d+next.d)
						{
							break;
						}//만약 더큰비용을 들여서 최단거리라면 break
						dis[i][next.v]=temp.d+next.d;
					}//불필요한 계산을 없애주는 가장 중요한 부분
					//만약 비용을 더들여서 같은지점에 도착했다면, 의미가 없다.
					//그렇기에 해당 노드에 가는데 비용부터, 허용된 비용까지 모두 최소 거리로 설정해준다
					pq.add(new Node(next.v,next.c+temp.c,temp.d+next.d));
				}
			}
		}
		int result=Integer.MAX_VALUE;
		for(int i=0;i<=M;i++)
		{
			result=Math.min(result, dis[i][N]);
		}
		System.out.println(result==Integer.MAX_VALUE? "Poor KCM":result);
	}
}

원래는 다익스트라 도중 다른 절차를 몇개 추가했다. 

원래는 해당비용에서만 값을 갱신해줬다면, 이 코드는 더큰 비용도 모두 갱신해주었다.

나는 이걸로 해결했다고 생각했는데 이게 웬걸?? 이것도 시간초과가 나왔다.

나는 여기서 더 이상 시간을 줄일 법이 생각이 안나서 구글에 검색해서 웬만한 블로그들의 글을 복붙해서 제출을 해봤다.

정말 다익스트라로 풀이를 한 모든 코드들이 다 시간초과가 나왔다

 

그러던 와중 새로운 신박한 풀이를 봤다.

바로 다익스트라가 아닌, 그냥 모든 값을 다 돌려보는 풀이였다. 놀랍게도 이 코드는 맞았다.

정답코드

import java.util.*;
import java.io.*;
class Node 
{
	int v;//정점
	int c;//가격
	int d;//시간
	Node(int v,int c,int d)
	{
		this.v=v;
		this.c=c;
		this.d=d;
	}
}
public class Main {

	public static int INF=100001;
	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());
		String[] s=br.readLine().split(" ");
		int N=Integer.parseInt(s[0]);
		int M=Integer.parseInt(s[1]);
		int K=Integer.parseInt(s[2]);
		ArrayList<Node>[] arr=new ArrayList[N+1];
		for(int i=1;i<=N;i++)
		{
			arr[i]=new ArrayList<Node>();
		}
		for(int i=0;i<K;i++)
		{
			s=br.readLine().split(" ");
			int u=Integer.parseInt(s[0]);
			int v=Integer.parseInt(s[1]);
			int c=Integer.parseInt(s[2]);//비용
			int d=Integer.parseInt(s[3]);//시간
			arr[u].add(new Node(v,c,d));//양방향이 아니다
		}
		int[][] dis=new int[M+1][N+1];//앞에는 비용, 뒤에는 노드번호, value는 시간
		for(int i=0;i<=M;i++)//
		{
			Arrays.fill(dis[i], INF);
		}
		dis[0][1]=0;//시작점은 초기화
		for(int i=0;i<=M;i++)
		{
			for(int j=1;j<=N;j++)
			{
				for(Node temp : arr[j])
				{
					if(i+temp.c<=M)
					{
						dis[i+temp.c][temp.v]=Math.min(dis[i+temp.c][temp.v], dis[i][j]+temp.d);
					}
				}
			}
		}
		int result=INF;
		for(int i=0;i<=M;i++)
		{
			result=Math.min(result, dis[i][N]);
		}
		System.out.println(result==INF? "Poor KCM":result);
	}
}

출처:

https://roamingman.tistory.com/46

백준 10217번 문제(KCM Travel) 파이썬(Python) 풀이 [로밍맨]

위 블로그는 파이썬으로 풀어서, 나는 그걸참고해서 JAVA로 풀었다.

 

혹시 이 문제를 다익스트라로 풀어서 시간초과가 안나고 맞은 분이 계시다면 꼭 댓글 달아주십쇼 ㅠㅠㅠ

진짜 궁금합니다.