[문제][알고스팟] 근거리네트워크 (LAN) (1)

문제 정보

• • 문제 ID
  • 시간 제한
  • 메모리 제한
  • 제출 횟수
  • 정답 횟수 (비율)
• • LAN
  • 1000ms
  • 65536kb
  • 1198
  • 444 (37%)
• • 출제자
  • 출처
  • 분류
• • JongMan
  • 알고리즘 문제 해결 전략
  • 보기

문제

근거리 네트워크(LAN, Local Area Network)는 가정, 학교, 혹은 회사 등의 제한된 공간 내의 컴퓨터들을 연결하는 네트워크입니다. 알고스팟 대학교에서는 캠퍼스의 일부 건물들만이 서로 근거리 네트워크로 연결되어 있었는데, 이번에 캠퍼스 정보화 사업의 일환으로 모든 건물을 모두 연결하려고 합니다. 모든 건물이 서로 연결되어 있다는 것은 건물 사이의 케이블을 이용해 모든 건물 간에 서로 직접/간접적으로 데이터를 주고받을 수 있다는 것을 의미합니다.

문제를 단순화하기 위해, 모든 건물들은 2차원 평면 위에 있는 점이라고 가정합시다. 두 건물을 직접 연결하려면 두 건물 사이의 거리 만큼의 케이블이 필요합니다. 케이블은 항상 두 건물만을 연결할 수 있으며, 두 케이블이 교차한다고 해서 두 케이블이 직접 연결된 것은 아닙니다.

각 건물들의 위치와 이미 설치된 케이블들에 대한 정보가 주어질 때, 모든 건물을 연결하기 위해 추가로 설치해야 할 케이블 길이의 최소 합을 계산하는 프로그램을 작성하세요.

입력

입력의 첫 줄에는 테스트 케이스의 수 C (C <= 50) 가 주어집니다. 각 테스트 케이스의 첫 줄에는 건물의 수 N (N <= 500) 과 이미 설치된 케이블의 수 M (M <= 2000) 이 주어집니다. 각 건물은 0번부터 N-1 번까지의 고유 번호로 구분합니다. 다음 줄에는 N 개의 정수로 0번부터 N-1 번까지 각 건물의 x 좌표가, 그 다음 줄에는 N 개의 정수로 y 좌표가 주어집니다. 각 좌표의 절대값은 1000 이하입니다. 그 후 M 줄에 각 2개의 정수로 각 케이블이 연결하는 두 건물의 번호가 주어집니다. 한 쌍의 건물을 연결하는 케이블이 두 개 이상 있을 수도 있습니다.

출력

각 테스트 케이스마다 한 줄에 추가로 설치해야 할 케이블의 총 길이를 출력합니다. 10-7 이하의 상대/절대 오차가 있는 답도 정답으로 인정합니다.

예제 입력

2
3 1
0 0 1
0 1 2
0 1
10 5
-7 -7 10 -4 10 -4 -5 0 -10 -6
6 8 -5 3 -4 6 -10 4 -7 10
9 7
7 3
9 7
5 0
8 6

예제 출력

1.4142135624 
29.7042202421 

---

오늘 컨디션이 안좋아서 어려운 문제는 아니었는데 너무 풀기싫었고 힘들었다. 
오랜 기간 생각이 너무 많아서 오히려 잡념이 파고들 수 있는 휴일에 컨디션이 더 안좋다.
그래도 지금까지처럼 짓눌려버리면 시간만 낭비할까봐 굳이 문제를 풀려고 했다.

이 문제는 알고스팟 최소스패닝 대표문제(예제)? 이다.
크루스칼, 프림 알고리즘 둘 다 사용해도 풀린다고 한다.

그런데 책 자체가 C기준이라 그런지 Java로 풀었을때 시간초과가 났다.

3개의 댓글이 있습니다.

• 
  Gyeongmin

  47ms나오신 분은 도대체 어떻게 푸신건지 ㅠㅠ...

  
  5년 전link

• 
  okpo65

  시간 제한이 너무 빡빡한거 같아요ㅠㅠ크루스칼 알고리즘은 ElonE인데 바로 시간 초과 나네요.. 책에는 4초여서 크루스칼로 했는데ㅜㅜ

  
  2년 전link

• 
  neo0603

  java 크루스칼, 프림 둘다 시간초과나는데 문제가 뭔지 알려주세요 ㅠ

  
  

이런 댓글들이 보이는걸로 봐선, 나만의 문제는 아닌것 같다.
일단 크루스칼로 풀이한 소스를 올리고 곧 프림 + 최적화 소스를 올릴 예정이다.

풀이 코드 (+크루스칼)

package apss;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Lan {
	
	public static int N,M,E;
	public static int node[][];
	public static int Set[];
	public static double Edge[][];
	public static double sum;
	public static int selected;
	
	 public static void main(String[] args) throws Exception{
		 
		 System.setIn(new FileInputStream("D:\\sample_input.txt"));
		 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		 BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		 
		 int T = Integer.parseInt(br.readLine().trim());
		 for(int tc=1; tc<=T; tc++) {
			 StringTokenizer st = new StringTokenizer(br.readLine());
			 N = Integer.parseInt(st.nextToken());
			 M = Integer.parseInt(st.nextToken());
			 E = N * N;
			 
			 node = new int[N][2];
			 Set = new int[N]; // start with 1. index 0 is not used.
			 Edge = new double[E][3];
			 sum = 0;
			 selected = 0;
			 
			 // x좌표
			 st = new StringTokenizer(br.readLine());
			 for(int i=0; i<N; i++) {
				 node[i][0] = Integer.parseInt(st.nextToken());
			 }
			 
			 // y좌표
			 st = new StringTokenizer(br.readLine());
			 for(int i=0; i<N; i++) {
				 node[i][1] = Integer.parseInt(st.nextToken());
			 }
			 
			 Arrays.fill(Set, -1);
			 
			 // join
			 for(int i=0; i<M; i++) {
				 st = new StringTokenizer(br.readLine());
				 int s = Integer.parseInt(st.nextToken());
				 int e = Integer.parseInt(st.nextToken());
				 join(s,e);
				 selected++;
			 }
			 
			 for(int i=0; i<E; i++) {
					 Edge[i][0] = i/N;
					 Edge[i][1] = i%N;
					 Edge[i][2] = Math.sqrt( 
							 Math.abs(node[(int)Edge[i][0]][0] - node[(int)Edge[i][1]][0]) * Math.abs(node[(int)Edge[i][0]][0] - node[(int)Edge[i][1]][0]) + 
							 Math.abs(node[(int)Edge[i][0]][1] - node[(int)Edge[i][1]][1]) * Math.abs(node[(int)Edge[i][0]][1] - node[(int)Edge[i][1]][1])
					 );
			 }
			 
			 Arrays.sort(Edge, new Comparator<double[]>() {

				@Override
				public int compare(double[] o1, double[] o2) {
					// TODO Auto-generated method stub
					return o1[2] - o2[2] > 0 ? 1 : -1;
				}

				 
			 });
			 
			 for(int i=0; i<E; i++) {
				 
				 if(group((int)Edge[i][0]) != group((int)Edge[i][1])) {
					 sum += Edge[i][2];
					 selected++;
					 join((int)Edge[i][0], (int)Edge[i][1]);  
				 }
				 
			 }
			 
			 
			 bw.flush();
			 bw.write(sum+"\n");
			 
			 
		 }
		 bw.close();
		 
		 
	 }
	 
	 // Union-Find : group
	 public static int group(int n) {  

	        if (Set[n] == -1) return n;  

	        return Set[n] = group(Set[n]); // path compression  

	    }  

	 //	Union-Find : join
	  public static void join(int a, int b) {  

	        int A = group(a), B = group(b);  

	        if (A != B) Set[A] = B;  

	    } 

}

---

생각해볼점

1. 사소한 테크닉이 부족한것 같다. 예를들어 Comparator 을 사용한 다중 배열의 정렬기준을 정의하는데, 아직도 혼동이 있다. 그리고 좀 더 차분히 생각하면 더 효율적인 자료구조를 활용할 수 있을텐데 마음이 급하다보니 직관적인 방법을 끝까지 밀고 나가려는 습관이 있다.

2. 하나의 알고리즘을 공부할때는 완벽하게 이해해야 응용을 할 수 있다. 진도를 나가는게 목적이 아니라 느리더라도 완벽하게 이해해야 응용이 가능하다.