[Java] 백준 23255 - 구름다리2

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

23255번: 구름다리 2

문제의 테스트케이스에 속으면 안되는 문제

 

구글에 없길래 내가 작성하는 글

 

설명을 잘 할 수 있을지 모르겠지만.. 일단 적어보자면

 

※ 주의할점

1. 빌딩 사이의 관계 M개의 순서를 정렬해주어야 함

- 두 빌딩의 값이 들어오면 작은 수를 A, 큰 수를 B로 할당해야 함

- 전체 관계 정렬시 작은 수인 A가 같다면 B가 작은 순으로 정렬한 후 구현해야 함

- 나는 입력값을 PQ에 담고, 나중에 꺼내서 각 빌딩의 색을 할당했음

2. 빌딩의 색이 도중에 바뀔 수 있음

- 빌딩의 값이 바뀌지 않는다고 생각하고 위 1번을 구현하게 된다면

  1-2 / 1-3 / 2-3 예제에서 2-3 관계를 정리할때 1-3의 관계를 생각하지 못한 채 결과가 1 2 1이 나옴

- 나는 객체 만들어서 연결된 빌딩의 색상의 주소값을 넣어주고,

   시간초과와 중복 값 등록을 방지하기 위해 HashSet을 이용함

3. 관계는 int[][] map으로 하지말자

- N이 100,000개인데, map을 이용하면 10만 x 10만개 → 메모리초과

- 이건 다들 알겠지.. (문제를 잘 읽지 않았던 나)

4. 주변에 있는지 확인할 때 contains 사용

- ArrayList사용해서 일일이 꺼내보고 비교하면 시간초과 남

- HashSet으로 바꾸고 contains하니까 통과됐다! 해시짱

 

 

 

구현보다 예외찾느라 수정이 오래 걸린 문제

 

[코드]

package BOJ;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.HashSet;
import java.util.PriorityQueue;


public class boj23255 {
	static class Building {
		int color = 0;
	}
	private static int N, M;
	private static Building[] color;
	private static HashSet<Integer>[] neighbor;
	private static PriorityQueue<int[]> pq;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String[] str = br.readLine().split(" ");
		N = Integer.parseInt(str[0]);
		M = Integer.parseInt(str[1]);
		
		color = new Building[N+1];
		neighbor = new HashSet[N+1];
		pq = new PriorityQueue<>(new Comparator<int[]>() {

			@Override
			public int compare(int[] o1, int[] o2) {
				if(o1[0]==o2[0])
					return o1[1]-o2[1];
				return o1[0]-o2[0];
			}
			
		});
		
		for(int i=1; i<=N; i++) {
			neighbor[i]= new HashSet<>();
			color[i] = new Building();
		}
			
		
		for(int i=0; i<M; i++) {
			str = br.readLine().split(" ");
			
			int ma = Integer.parseInt(str[0]);
			int mb = Integer.parseInt(str[1]);
			
			pq.add(new int[] {Math.min(ma, mb),Math.max(ma, mb)});
		}
		
		while(!pq.isEmpty()) {
			int[] p = pq.poll();
			
			int a = p[0];
			int b = p[1];
			
			if(color[a].color==0)
				color[a].color=1;
			
			neighbor[b].add(color[a].color);
			
			for(int j=1; j<=N; j++) {
				if(!neighbor[b].contains(j)) {
					color[b].color = j;
					break;
				}
			}
		}
		
		StringBuilder sb = new StringBuilder();
		for(int i=1; i<=N; i++) {
			if(color[i].color==0)
				color[i].color=1;
			
			sb.append(color[i].color+" ");
		}
		System.out.println(sb.toString().trim());
	}
}