모각소 3주차 활동 (백준 1865번 Java & 토이 프로젝트 계획)

1865번 웜홀 문제

이 문제는 음의 사이클을 갖는 그래프인지 검출하는 문제와 똑같이 접근할 수 있다. 출발점에서 다시 출발점으로 돌아올 때 오히려 시간이 역행한다는 경우는 음의 사이클이 존재한다는 것으로 문제를 재해석할 수 있다.
음의 사이클을 검출할 수 있어야하므로 벨만포드 또는 플로이드 워샬로 접근할 수 있다. 이 중 한 출발점에서 음의 사이클을 검출하면 다른 노드들을 출발점으로 설정하지 않아도 되므로 벨만포드가 더 실행시간이 짧을 것이라 생각했다.

import java.util.*;
import java.io.*;
//같은 패키지에 node class가 이미 있어서 클래스 이름을 node2로 지정
class Node2{
	int end, time;
	
	public Node2(int end, int time) {
		this.end = end;
		this.time = time;
	}
}

public class No1865 {
	static final int INF = 1000000000;
    //한 정점에서 다른 정점의 최단거리를 저장할 dist int 배열
	static int[] dist;
    //정점에 이어진 간선들의 정보를 저장할 weight list 배열
	static ArrayList<Node2>[] weight;

	public static void main(String[] args) throws Exception{
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		 BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int test_case = Integer.parseInt(bf.readLine());
		StringBuilder sb = new StringBuilder();
		for(int tc = 0; tc < test_case; tc++) {
			StringTokenizer st = new StringTokenizer(bf.readLine());
			int n = Integer.parseInt(st.nextToken());
			int m = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());
			dist = new int[n+1];
			
			weight = new ArrayList[n+1];
			for(int i = 0; i < n+1; i++) {
				weight[i] = new ArrayList<>();
			}
			//일반 도로 추가
			for(int i = 0; i < m; i++) {
				st = new StringTokenizer(bf.readLine());
				int start = Integer.parseInt(st.nextToken());
				int end = Integer.parseInt(st.nextToken());
				int time = Integer.parseInt(st.nextToken());
				weight[start].add(new Node2(end, time));
				weight[end].add(new Node2(start, time));
			}
			// 웜홀 추가
			for(int i = 0; i < w; i++) {
				st = new StringTokenizer(bf.readLine());
				int start = Integer.parseInt(st.nextToken());
				int end = Integer.parseInt(st.nextToken());
				int time = Integer.parseInt(st.nextToken());
				weight[start].add(new Node2(end, -time));
			}
			
            //1부터 n까지 정점을 출발로 설정해보고 음의 사이클 있는지 검사
			boolean minusCycle = false;
			for(int i = 1; i <= n; i++) {
				if(bellmanFord(i,weight,n)) {
					minusCycle = true;
					sb.append("YES\n");
					break;
				}
			}
			if(!minusCycle) {
				sb.append("NO\n");
			}
		}
		bw.write(sb.toString());
		bw.flush();
	}
	
	public static boolean bellmanFord(int start, ArrayList<Node2>[] weight, int n) {
		Arrays.fill(dist, INF);
		dist[start] = 0;
		boolean update = false;
		//모든 간선 살펴보는 것을 n-1번 반복
		for(int i = 1; i < n; i++) {
			update = false;
			for(int j = 1; j <= n; j++) {
				for(Node2 node : weight[j]) {
					if(dist[node.end] > dist[j] + node.time) {
						dist[node.end] = dist[j] + node.time;
						update = true;
					}
				}
			}
			//bellmanFord는 n-1번 만큼 모든 간선을 살펴보는 것이므로
			//중간에 update가 없다면 다음번에도 update가 없다는 것을 알 수 있다
			//그래서 update가 없을 때 break를 해줘야 시간 초과가 나지 않는다!!
			if(!update) {
				break;
			}
		}
		if(update) {
			for(int j = 1; j <= n; j++) {
				for(Node2 node : weight[j]) {
					if(dist[node.end] > dist[j] + node.time) {
						return true;
					}
				}
			}
		}
		return false;
	}
}

이 문제에서 배운 Java 스킬

ArrayList배열을 선언하는 방법
ArrayList<Generic\>[] list = new ArrayList<>()[]; 이렇게 선언하면 될 것 같았지만, 막상 실제로 해보면 오류가 뜬다. 해결하기 위해 검색해본 결과
ArrayList<Generic\>[] list = new ArrayList[n]; 으로 선언해주고 0부터 n-1까지 list[i] = new ArrayList<>(); 로 초기화 해줘야한다

Cannot make a static reference to the non-static field 오류
main 함수는 public static이므로 main함수와 같은 class내에 함수나 필드를 이용할려면 static으로 선언해줘야한다.

최상위(outer) private class는 쓸모없다
같은 패키지 내에 node class가 이미 존재해서 다른 소스의 node class를 private로 선언하는 뉴비스러운 행동을 했다. node class가 inner class였다면 상관없지만 그때도 outer class로 선언했기 때문에 이번에만 Node2라는 임시 class 이름을 사용했다. 다음부턴 Main class내에 private로 선언하거나 다른 package를 만들자
p.s import하면 다른 package에 선언된 public class를 이용할 수 있다

Arrays.fill 함수 이용해서 배열 같은 값 넣어주기
Arrays.fill("넣을 배열", "넣을 값")

모각소(모여서 각자 소프트웨어) 3주차에 생긴 새로운 계획

SCPC 2차 예선 진출이 모호해진 가운데 막연히 코테 준비만 하기엔 의욕이 없을 것 같아 새로운 목표를 설정하기로 팀원과 이야기했다. 마침 2명의 팀원이 자바 스프링을 공부하는 중이고 백엔드에 관심이있어서, 예전에 내가 프론트를 다뤄봤던 점을 살려 Microsoft사의 ToDo라는 일정관리 홈페이지를 클론코딩 + 사이드 업그레이드를 해보기로 계획을 세웠다.
앞으로 올릴 게시글엔 프로젝트를 진행하면서 새로 알게된 점들이나 유용한 것들을 올려서 공유하고자 한다.