글 읽기 - 예제 답이 왜 2인가요?

kkw9219 4년 전 0

문제를 풀긴했는데, 왜 예제 입력2에서 출력 값이 "2"인지 이해가 안되서요?

3이 되야 하는게 아닌지요?

예제 입력 값.

10 3

1 1

1 3

1 8

출력 값 : 2라고 함.

================================= 아래는 제가 생각한 풀이

1 2

0 1 2 (*)

1 2

0 1 2 (*)

1 2

0 1 2 (*)

=> 0 이 출발점이라고 하면 2가 되는 순간 "1 3" 과"1 8"이 y 기준으로 접하게 되고,

3이 되면 합쳐지게 됩니다...

혹시 푸신 분 있으시면 답변 부탁드립니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	static int N, K;
	static int num_of_cul;
	static int [] parent = new int [4000001];
	static int [][] val = new int [2001][2001];
	static int [] dx = new int [] { 1, -1, 0, 0 };
	static int [] dy = new int [] { 0, 0, 1, -1 };
	static PriorityQueue<int []> pq = new PriorityQueue<int[]>(1000000, new Comparator<int []>() {
		public int compare(int[] o1, int[] o2) {
			return o1[2] - o2[2];
		}
	});
		
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		//System.setIn(new FileInputStream("Cul_input4.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer str = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(str.nextToken());
		K = Integer.parseInt(str.nextToken());
		
		for(int i = 1; i <= N; i++) {
			for(int j = 1; j <= N; j++) {
				parent[i + (j-1)*N] = i + (j-1)*N;
			}
		}
		int x, y;
		for(int i = 1; i <= K; i++) {
			str = new StringTokenizer(br.readLine());
			x = Integer.parseInt(str.nextToken());
			y = Integer.parseInt(str.nextToken());
			val[x][y] = -1; //source 표기
			num_of_cul++;
			System.out.printf("pq: %d %d\n", x, y);
			pq.add(new int [] {x, y, 1});			
		}
		if(pq.size() == 1) {
			bw.write(String.valueOf(0));
			bw.newLine();
		}
		num_of_cul--;
		while(!pq.isEmpty()) {
			int [] c;
			int x1, y1, k;
			c = pq.poll();
			x1 = c[0]; y1 = c[1]; k = c[2];			
			
			for(int i = 0; i < 4; i++) {
				int nx = x1 + dx[i];
				int ny = y1 + dy[i];
				
				if(nx >= 1 && nx <= N && ny >= 1 && ny <= N) {
					if(find(x1 + (y1-1)*N) != find(nx + (ny-1)*N)) {
						union(x1 + (y1-1)*N, nx + (ny-1)*N);
						//서로 다른 문화가 서로 만난 경우 문화가 합쳐질 것이므로 문화 수를 줄인다.
						if(val[nx][ny] != 0)
							--num_of_cul;
						//서로 합쳐야 할 문화가 다 통일됨.
						if(num_of_cul == 0 && val[nx][ny] > 0) {
							bw.write(String.valueOf(k));
							bw.newLine();
							bw.flush();
							bw.close();
							return;																				
						}
						//초기 값을 가진 두 문화가 헙쳐지는 경우, 즉 문화가 서로 인접된 경우임.
						//문화가 뭉쳐서 1개인 경우에 해당함.
						else if(num_of_cul == 0 && val[nx][ny] == -1) {
							bw.write(String.valueOf(0));
							bw.newLine();
							bw.flush();
							bw.close();
							return;
						}
						//서로 인접한 문화를 합치는 과정임. 인접 문화 이므로 Queuing하지 않는다.
						else if(num_of_cul > 0 && val[nx][ny] == -1) {							
							System.out.printf("Common S : %d %d -- %d %d, num_of_cul:%d\n", x1, y1, nx, ny, num_of_cul);
							continue;
						}
						val[nx][ny] = k; //확장 영역 표시
						System.out.printf("val org: %d %d, ex:%d %d => %d\n", x1, y1, nx, ny, k);
 						pq.add(new int [] {nx, ny, k+1});	
					}
				}				
			}			
		}		
	}
	static int find(int a) {
		if(a == parent[a]) return a;
		return parent[a] = find(parent[a]);
	}
	static void union(int a, int b) {
		int rootA = find(a);
		int rootB = find(b);
		
		if(find(a) != find(b)) {
			parent[rootA] = b;
			//System.out.printf("union %d, %d 	(parent : %d)\n", a, b, b);			
		}
	}
}

dudrb0139 4년 전 0

문제.

만약 두 인접하는 지역에 다른 문명이 전파되었거나, 한 지역에 둘 이상의 다른 문명이 전파된다면 이 문명들은 결합된다.

여기서 두 인접하는 지역에 다른 문명이 전파되었거나는 문명이 마주한 경우이고,

한 지역에 둘 이상의 다른 문명이 전파된다면 이 문명들은 결합된다는 문명이 합쳐지는 경우입니다.

문제에서는 두 경우 모두 문명이 결합된다고 봅니다.

kkw9219 4년 전 0

dudrb0139 님 말씀하신거 이해가 되질 않습니다. "1 8" 기준에서 보면 가장 가까운 것은 "1 3"이고, "1 3" 과"1 8"를 기준으로 보면 거리가 y축 기준으로 5이기 때문에, 확장 count가 3은 되야 서로 결합되는 것이 아닌지요? 2 확장 되면 결합은 되지 않고, 바로 인접하는 경우입니다.

kkw9219 4년 전 1

문제를 잘 읽어봤어야 했는데. 이제야 이해했습니다. 댓글 달아주신 dudrb0139 님 감사합니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

예제 답이 왜 2인가요?

kkw9219 4년 전 0

dudrb0139 4년 전 0

kkw9219 4년 전 0

kkw9219 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말