[백준/파이썬/14868] 문명

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

14868번: 문명

Problem

• 인류의 역사를 돌이켜보면, 문명의 발전은 독자적으로 진행되기도 하지만 서로 다른 문명이 만나 결합되기도 한다. 여러분은 이 가설을 바탕으로, 세계 문명의 발전 과정을 시뮬레이션 해보려고 한다.
• 세계의 크기, 문명 발상지의 수 및 위치를 입력으로 받아 모든 문명이 하나로 결합될 때까지 걸리는 최소 햇수를 구하는 프로그램을 작성하시오.

조건 

• 두 정사각형 (a, b)와 (a′, b′)은 다음 두 조건 중 하나만 만족할 때 서로 인접해 있다고 하자.
  • |a - a′| = 1 이고 b = b′.
  • |b - b′| = 1 이고 a = a′.
• 각 정사각형에 해당하는 공간은 문명 지역이거나, 미개 지역이다. 문명의 최초 발상지는 문명 지역이며, 만약 문명 최초 발상지끼리 인접해 있다면, 이들은 처음부터 하나로 결합된다.
• 한 해가 지날 때마다, 문명 지역은 자신과 인접한 지역에 문명을 전파한다. 정사각형 (a, b)가 문명 지역이면, 다음 해에는 세계의 경계를 넘지 않는 한 이 정사각형과 인접한 네 정사각형 (a+1, b), (a-1, b), (a, b+1), (a, b-1)에 문명이 전파된다.
• 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 세계의 크기를 나타내는 정수 N(2 ≤ N ≤ 2,000)과
• 문명 발상지의 수 K(2 ≤ K ≤ 100,000)가 주어진다.
• 다음 K줄에는 한 줄에 하나씩 문명 발상지에 해당하는 정사각형의 위치 (x, y)를 나타내는 두 자연수 x와 y가 주어진다. (1 ≤ x, y ≤N)

SOL

 

완전탐색

1. 입력받은 K를 board에 반영해준다.
   • 각각 다른 문명이니까, 문명에 numbering을 해서 다른 문명임을 표시해준다.
2. 인접해있는 문명은 합쳐준다.
   • 인접해있는 문명은 하나로 합쳐준다. numbering이 다르니까, map에 직접 접근해서, 인접해있는 친구로 바꿔준다.
3. 합쳐진 문명을 가지고, BFS로 문명을 전파시킨다.
   
   • 문명이 사방으로 전파되기 시작한다. 
   • 문명이 퍼질 때 마다, 모든 문명이 하나가 되었는지 확인을 해야한다.
     • 문명이 퍼진걸 반영한 board를 가지고, DFS/BFS를 탐색해서, 모든 문명의 시작지에 도달할 수 있는지 확인한다.
4. 문명의 시작지에 다 도달을 할 수 있다면, 그때의 year을 출력해준다. 

시간 복잡도를 계산해주면, O(K) + O(N^2)+O(N^2)*O(N^2)이 된다. (최악의 경우, 맵 전체를 다 돌아아하므로, N^4이 된다. TL이 무적권 난다) 완전탐색만으로는, 풀수가 없는 문제이고, Optimal(최적화)를 해줘야한다.

 

Union-Find

문명이 하나의 문명이냐/아니냐를 판단하는 방법을 줄이면, N^2으로 통과가 가능하다.

 

친구 이냐/아니냐, 같은 조이냐/아니냐 등등 어떤 하나의 개념에 속해있는지 ,안속해있는지(서로소이냐/합집합의 관계냐) 판단하기위한 효율적인 방법 중 하나는 union -find 구조를 사용하는거다.

 

문명의 숫자(K)가 1일때 , 반복을 멈추고, year을 출력하면 된다.

만약, 같은 문명에 속하게 된다면, 그 둘을 같은 문명이라고 취급하고, K를 1개 줄여주면 된다.(문명이 하나가 사라졌기 때문에)

순서도가 아래와 같이 수정될거임

1. 입력받은 K를 board에 반영해준다.
   • 각각 다른 문명이니까, 문명에 numbering을 해서 다른 문명임을 표시해준다.
   • 문명 dq에 각각의 문명의 위치를 append한다.
2. 인접해있는 문명은 합쳐준다.
   • 인접해있는 문명은 하나로 합쳐준다. numbering이 다르니까, map에 직접 접근해서, 인접해있는 친구로 바꿔준다.
     • 문명의 위치를 pop하고, bfs를 위한 dq에 append 해준다.
     • 인접해있는지 탐색을 시작한다.
       • 범위 chk를 해준다. 다른 문명과 접해있는지 확인해준다.
       • 다른 문명과 접해있다면, 하나의 문명으로 합쳐준다. 이때, 문명이 합쳐지면 , K-=1을 해준다.
3. BFS로 문명을 전파시킨다.
   
   • 문명이 사방으로 전파되기 시작한다. 
   • 문명이 퍼진 곳의 좌표들(새롭게 문명이된곳)들을 문명의 dq에 반영해준다.
4. 위 과정을 K==1이 될때까지 반복한다. 

#일반적인 BFS로 탐사한다면, TL발생
from collections import deque
import sys
input = sys.stdin.readline

N,K = map(int,input().split())
dx=(1,0,-1,0)
dy=(0,1,0,-1)
maps=[[0 for _ in range(2001)] for _ in range(2001)]
civil=[x for x in range(100001)]
civil_dq=deque()
bfs_dq=deque()

def is_valid_coord(y,x):
    return 0<=y<N and 0<=x<N

def find(target):
    if civil[target] == target:
        return target
    civil[target] = find(civil[target])
    return civil[target]

def union(a,b):
    a=find(a)
    b=find(b)
    if a !=b:
        civil[a]=b

def is_same_parent(a,b):
    a=find(a)
    b=find(b)
    return a == b

def union_civil():
    global K
    while civil_dq:
        y,x=civil_dq.popleft()
        bfs_dq.append((y,x))
        for k in range(4):
            ny=y+dy[k]
            nx=x+dx[k]
            # 범위를 벗어나거나, 문명이 없다면 Pass
            if (not is_valid_coord(ny,nx)) or maps[ny][nx]==0:
                continue
            cur_civil=maps[y][x]
            neighbor_civil=maps[ny][nx]
            #문명의 번호가 같거나, 같은 문명에 속해있다면
            if (cur_civil ==neighbor_civil) or is_same_parent(cur_civil,neighbor_civil):
                continue
            # 인접하면서, 문명의 번호가 다르거나, 다른 문명에 속해있는 경우만 남게됨.
            union(cur_civil,neighbor_civil)
            K-=1

def bfs():
    while bfs_dq:
        y,x = bfs_dq.popleft()
        for k in range(4):
            ny=y+dy[k]
            nx=x+dx[k]
            if (not is_valid_coord(ny,nx)) or maps[ny][nx] !=0:
                continue
            maps[ny][nx]=maps[y][x]
            civil_dq.append((ny,nx))

for i in range(K):
    y,x=map(int,input().split())
    maps[y-1][x-1] = i+1
    civil_dq.append((y-1,x-1))

year=0
while K>1:
    #문명 합치기
    union_civil()
    if K==1:
        print(year)
        break
    #문명이 퍼진다.
    bfs()
    year +=1

pypy3로 제출해서 100점을 맞았습니다.