문명 > 문제은행

본문 바로가기


문제은행

3079 : 문명

제한시간: 1Sec    메모리제한: 64mb
해결횟수: 0회    시도횟수: 0회    채점준비중입니다.



인류의 역사를 돌이켜보면, 문명의 발전은 독자적으로 진행되기도 하지만 서로 다른 문명이 만나 결합되기도 한다. 여러분은 이 가설을 바탕으로, 세계 문명의 발전 과정을 시뮬레이션 해보려고 한다.

 

세계를 N×N의 2차원 공간으로 생각할 수 있다. 즉, 1×1 크기의 정사각형이 가로, 세로로 각각 N개씩 쌓여있는 형태로 생각할 수 있다. 가장 왼쪽 아래 정사각형은 (1,1), 가장 오른쪽 위 정사각형은 (N,N)위치에 있다. 두 정사각형 (a,b)와 (a’, b’)은 다음 두 조건 중 하나만 만족할 때 서로 인접해 있다고 하자.

 

● |a - a’| = 1 이고 b = b’,
● |b - b’| = 1 이고 a = a’.

 

문명의 최초 발상지는 모두 서로 다른 K곳에 있다. 각 정사각형에 해당하는 공간은 문명 지역이거나, 미개 지역이다. 문명의 최초 발상지는 문명 지역이며, 만약 문명 최초 발상지끼리 인접해 있다면, 이들은 처음부터 하나로 결합된다. 한 해가 지날 때마다, 문명 지역은 자신과 인접한 지역에 문명을 전파한다. 정사각형 (a.b)가 문명 지역이면, 다음 해에는 세계의 경계를 넘지 않는 한 이 정사각형과 인접한 네 정사각형 (a+1,b), (a-1,b), (a,b+1), (a,b-1)에 문명이 전파된다. 만약 두 인접하는 지역에 다른 문명이 전파되었거나, 한 지역에 둘 이상의 다른 문명이 전파된다면 이 문명들은 결합된다.

 

예를 들어, 다음과 같이 5×5 크기의 세계에 4곳의 정사각형 (1,1), (2,1), (2,5), (5,2)가 문명의 발상지라고 하자. 정사각형 (1,1), (2,1)의 문명은 인접해 있으므로 처음부터 결합되어 있다. 1년 후 문명이 전파된 지역은 오른쪽 그림과 같고, 2년 후에 문명이 전파된 지역은 아래 그림과 같다. 이때 모든 문명은 서로 결합되어 하나의 문명이 된다. (2,5)에서 발상한 문명과 (5,2)에서 발상 한 문명은 직접적으로 결합되지는 않았지만, (1,1), (2,1)에서 발상한 문명을 통하여 결합됨에 주의하라.

08b6f023ea4f0ddc33a2459594e06b23_1502450
 

세계의 크기, 문명 발상지의 수 및 위치를 입력으로 받아 모든 문명이 하나로 결합될 때까지 걸리는 최소 햇수를 구하는 프로그램을 작성하시오.
 


표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 세계의 크기를 나타내는 정수 N(2 ≤ N ≤ 2,000)과 문명 발상지의 수 K(1 ≤ K ≤ 100,000)가 주어진다. 다음 K줄에는 한 줄에 하나씩 문명 발상지에 해당하는 정사각형의 위치 (x, y를 나타내는 두 자연수 x와 y가 주어진다. (1 ≤ x, y ≤ N)


표준 출력으로 모든 문명이 하나로 결합되는데 걸리는 최소 햇수를 정수로 출력한다.

부분문제의 제약 조건 
● 부분문제 1: 전체 점수 100점 중 19점에 해당하며 2 ≤ N ≤ 100, 2 ≤ K ≤ 100 이다.
● 부분문제 2: 전체 점수 100점 중 35점에 해당하며 2 ≤ N ≤ 1,000, 2 ≤ K ≤ 100,000 이다.
● 부분문제 3: 전체 점수 100점 중 46점에 해당하며 원래의 제약조건 이외에 아무 제약조건이 없다.

[Copy]
5 4 
1 1 
2 1 
2 5 
5 2
[Copy]
2


[Copy]
10 3 
1 1 
1 3 
1 8
[Copy]
2




HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.