알고리즘문제풀이/백준

[BOJ]1865_웜홀_Java

초보개발자.. 2021. 6. 14. 22:29

--문제--

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

 

1865번: 웜홀

첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500),

www.acmicpc.net

 

--문제 접근--

처음 문제를 봤을 때는 그래프와 DFS를 이용하여 지점을 거친 뒤 start지점으로 왔을 때 음수인지 확인만 하여 답을 구하려고 노력하여봤습니다. 하지만 그렇게 하면 시간 초과가 떠서 좋은 방법이 어떤 것이 있는지 생각을 하다 벨만 포드 알고리즘을 이용하여 풀었습니다.

--시간 초과--

package Class4;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class BOJ_1865웜홀 {
	static class Node{
		int node,weight;
		public Node(int node, int weight) {
			super();
			this.node = node;
			this.weight = weight;
		}
	}
	static int N,M,W;
	static boolean check;
	static boolean[] visit;
//	static int[][] map;
	static List<Node>[] graph;
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int TC=sc.nextInt();
		for(int t=0;t<TC;t++) {
			N=sc.nextInt();
			M=sc.nextInt();	
			W=sc.nextInt();
			graph=new ArrayList[N+1];
			for(int i=0;i<=N;i++)graph[i]=new ArrayList<>();
			for(int i=0;i<M;i++) {
				int from=sc.nextInt();
				int to=sc.nextInt();
				int weight=sc.nextInt();
				graph[from].add(new Node(to,weight));
				graph[to].add(new Node(from,weight));
			}
			for(int i=0;i<W;i++) {
				int from=sc.nextInt();
				int to=sc.nextInt();
				int weight=sc.nextInt();
				graph[from].add(new Node(to,-weight));
			}
			visit=new boolean[N+1];
			check=false;
			for(int i=1;i<=N;i++) {
				dfs(i,i,0);
			}
			if(check)System.out.println("YES");
			else System.out.println("NO");
		}
		
	}
	private static void dfs(int start,int current,int value) {
		if(start==current&&value!=0) {
			if(value<0)check=true;
			return;
		}
		for(Node cur:graph[current]) {
			if(!visit[cur.node]) {
				visit[cur.node]=true;
				dfs(start,cur.node,value+cur.weight);
				visit[cur.node]=false;
			}
		}
	}

}

--정답 코드--

package Class4;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class BOJ_1865웜홀 {
	static class Node{
		int node,weight;
		public Node(int node, int weight) {
			super();
			
			this.node = node;
			this.weight = weight;
		}
	}
	static int N,M,W;
	static boolean check;
	static boolean[] visit;
	static int[] result;
//	static int[][] map;
	static List<Node>[] graph;
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int TC=sc.nextInt();
		for(int t=0;t<TC;t++) {
			N=sc.nextInt();
			M=sc.nextInt();	
			W=sc.nextInt();
			graph=new ArrayList[N+1];
			for(int i=0;i<=N;i++)graph[i]=new ArrayList<>();
			for(int i=0;i<M;i++) {
				int from=sc.nextInt();
				int to=sc.nextInt();
				int weight=sc.nextInt();
				graph[from].add(new Node(to,weight));
				graph[to].add(new Node(from,weight));
			}
			for(int i=0;i<W;i++) {
				int from=sc.nextInt();
				int to=sc.nextInt();
				int weight=sc.nextInt();
				graph[from].add(new Node(to,-weight));
			}
			result =new int[N+1];
			Arrays.fill(result, 99999999);
//			visit=new boolean[N+1];
//			check=false;
			result[1]=0;
			boolean update=false;
			out:for(int i=1;i<=N;i++) {
				update=false;
				for(int j=1;j<=N;j++) {
					for(Node cur : graph[j]) {
						if(result[cur.node]>result[j]+cur.weight) {
							result[cur.node]=result[j]+cur.weight;
							update=true;
							if(i==N) {
								update=true;
								break out;
							}
						}
					}
					
				}
			}
			
			if(update)System.out.println("YES");
			else System.out.println("NO");
		}
		
	}
//	private static void dfs(int start,int current,int value) {
//		if(start==current&&value!=0) {
//			if(value<0)check=true;
//			return;
//		}
//		for(Node cur:graph[current]) {
//			if(!visit[cur.node]) {
//				visit[cur.node]=true;
//				dfs(start,cur.node,value+cur.weight);
//				visit[cur.node]=false;
//			}
//		}
//	}

}
댓글수0