[백준] 1240번 노드사이의 거리 - Java

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

1240번: 노드사이의 거리

---

문제

---

코드

Try 1. 시간초과가 뜬 코드입니다. - 코드 길이 1005B

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int N, M;
		N = sc.nextInt();
		M = sc.nextInt();
		sc.nextLine();
		
		int[][] matrix = new int[N][N];
		
		int row, col;
		int value;
		
		for(int i = 0 ; i < (N-1) ; i++) {
			row = sc.nextInt();
			col = sc.nextInt();
			value = sc.nextInt();
			matrix[row-1][col-1] = value;
			matrix[col-1][row-1] = value;
			sc.nextLine();
		}
		
		int node1, node2;
		int[] ans = new int[M];
		
		for(int i = 0 ; i < M ; i++) {
			node1 = sc.nextInt();
			node2 = sc.nextInt();
			int sum = 0;
			int pre = node1 - 1;
			int end = node2 - 1;
			
			int next = 0;
			
			while(true) {
				if(pre == end) {
					break;
				}
				
				if(matrix[pre][next] > 0) {
					sum += matrix[pre][next];
					pre = next;
					next = 0;
				}
				else {
					next++;
				}
			}
			ans[i] = sum;
			sc.nextLine();
			
		}
		for(int i = 0 ; i < M ; i++) {
			System.out.println(ans[i]);
		}
	}
}

• BufferedReader 와 BufferedWriter을 사용하여 시간을 줄일 수 있다는 것을 알게 되었습니다.
• 이때까지만 해도 이게 아주 간단한.. 문제인 줄 알았습니다..

 

Try 2. 틀렸습니다가 뜬 코드입니다. - 코드 길이 2187B

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.IOException;

public class Main{
	
	static int[][] matrix;
	static int N, M;
	static boolean[] visited;
	static int[] dist;
	
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		String[] NM = new String[2];
		
		NM = bf.readLine().split(" ");
		
		N = Integer.parseInt(NM[0]);
		M = Integer.parseInt(NM[1]);
		
		matrix = new int[N][N];
		for(int i = 0 ; i < N ; i++) {
			for(int j = 0 ; j < N ; j++) {
				if(i == j) {
					matrix[i][j] = 0;
				}
				else {
					matrix[i][j] = 100001;					
				}
			}
		}
		
		int row, col;
		int value;
		
		String[] nodeArr = new String[3];
		
		for(int i = 0 ; i < (N-1) ; i++) {
			nodeArr = bf.readLine().split(" ");

			row = Integer.parseInt(nodeArr[0]) - 1;
			col = Integer.parseInt(nodeArr[1]) - 1;
			value = Integer.parseInt(nodeArr[2]);
			matrix[row][col] = value;
			matrix[col][row] = value;
		}
		
		String[] QArr = new String[2];
		int node1, node2;
		int[] ans = new int[M];
		
		for(int i = 0 ; i < M ; i++) {
			visited = new boolean[N];
			dist = new int[N];
			for(int j = 0 ; j < N ; j++) {
				dist[j] = 100001;
			}
			
			QArr = bf.readLine().split(" ");
			node1 = Integer.parseInt(QArr[0]) - 1;
			node2 = Integer.parseInt(QArr[1]) - 1;
			
			int pre = node1;
			
			dist[pre] = 0;
			
			for(int j = 0 ; j < N ; j++) {
				if(pre == node2) {
					break;
				}
				pre = dijktra(pre);
				if(pre == -1) {
					break;
				}
			}
			
			ans[i] = dist[node2];
		}
		for(int i = 0 ; i < M ; i++) {
			bw.write(Integer.toString(ans[i]) + "\n");
		}
		bw.flush();
		bw.close();
	}
	
	public static int dijktra(int pre) {
		int min = 100001;
		int next = -1;
		visited[pre] = true;
		for(int i = 0 ; i < N ; i++) {
			if(dist[i] >= matrix[pre][i] + dist[pre]) {
				dist[i] = matrix[pre][i] + dist[pre];
				if(min >= dist[i] && !visited[i]) {
					min = dist[i];
					next = i;
				}
			}
		}
		return next;
	}
}

• 다익스트라 알고리즘으로 문제를 해결하려고 했습니다. 그런데도 되지 않았습니다.
• 제가 짠 다익스트라 알고리즘 코드는 한 방향으로만 갈 수 있기 때문이었습니다.

• 쉽게 말해서, 이런 그래프가 그려질 경우에 1에서 5로 가는 건 찾지 못한다는 뜻입니다. (...)
  그래서 다익스트라와 그래프 탐색이라는게 공존할 수 있는건가? 라는 생각을 했는데, 생각해보니까 돌아가는 걸 생각하지 못했더라고요. visited 배열을 만들고서 활용할 줄을 몰랐던 겁니다. 아놔~~~~~~~ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 안 웃김요.

 

Try 3. 시간초과가 뜬 코드입니다. - 코드 길이 2207B

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.IOException;

public class Main{
	static int[][] matrix;
	static int N, M;
	static boolean[] visited;
	static int[] dist;
	
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		String[] NM = new String[2];
		
		NM = bf.readLine().split(" ");
		
		N = Integer.parseInt(NM[0]);
		M = Integer.parseInt(NM[1]);
		
		matrix = new int[N][N];
		for(int i = 0 ; i < N ; i++) {
			for(int j = 0 ; j < N ; j++) {
				if(i == j) {
					matrix[i][j] = 0;
				}
				else {
					matrix[i][j] = 100001;					
				}
			}
		}
		
		int row, col;
		int value;
		
		String[] nodeArr = new String[3];
		
		for(int i = 0 ; i < (N-1) ; i++) {
			nodeArr = bf.readLine().split(" ");

			row = Integer.parseInt(nodeArr[0]) - 1;
			col = Integer.parseInt(nodeArr[1]) - 1;
			value = Integer.parseInt(nodeArr[2]);
			matrix[row][col] = value;
			matrix[col][row] = value;
		}
		
		String[] QArr = new String[2];
		int node1, node2;
		int[] ans = new int[M];
		
		for(int i = 0 ; i < M ; i++) {
			visited = new boolean[N];
			dist = new int[N];
			for(int j = 0 ; j < N ; j++) {
				dist[j] = 100001;
			}
			
			QArr = bf.readLine().split(" ");
			node1 = Integer.parseInt(QArr[0]) - 1;
			node2 = Integer.parseInt(QArr[1]) - 1;
			
			int pre = node1;
			
			dist[pre] = 0;
			
			while(true) {
				if(pre == node2) {
					break;
				}
				pre = dijktra(pre);
				if(pre == -1 && pre != node2) {
					pre = node1;
				}
			}
			
			ans[i] = dist[node2];
		}
		for(int i = 0 ; i < M ; i++) {
			bw.write(Integer.toString(ans[i]) + "\n");
		}
		bw.flush();
		bw.close();
	}
	
	
	public static int dijktra(int pre) {
		int min = 100001;
		int next = -1;
		visited[pre] = true;
		for(int i = 0 ; i < N ; i++) {
			if(!visited[i] && dist[i] >= matrix[pre][i] + dist[pre]) {
				dist[i] = matrix[pre][i] + dist[pre];
				if(min >= dist[i] && !visited[i]) {
					min = dist[i];
					next = i;
				}
			}
		}
		return next;
	}
}

• 왜.. 안 되는지 모르겠네요. 3중 for문도 돌아가는 것 같던데 음... 다익스트라 알고리즘에서 시간을 더 줄일 방법이 있을까요? 막히면 바로 이전 노드로 돌아가는 방법을 찾으려다가 포기했습니다. 오히려 시간 복잡도가 늘어날 것 같아서요.

https://velog.io/@seongwon97/BaekJoon-1240-%EB%85%B8%EB%93%9C%EC%82%AC%EC%9D%B4%EC%9D%98-%EA%B1%B0%EB%A6%AC-Java

제출하기 위해 참고한 블로그입니다. 그대로 복붙하는 수 밖에 없어서.. 링크로만 남겨두겠습니다. 저의 시도를 봐주셔서 감사합니다.

---

후기

오랜만이죠~ 개강하고서 바로 시작하려고는 했는데 할 기분이 아니라 일주일은 지금까지 고생한 저를 위해 파업했습니다. ㅎㅎ

앞으로도 열심히 해보이겠습니다~