14868. 문명 - 유니온 파인드. 백준. 파이썬

사용한 알고리즘 / 자료구조

1. 델타를 이용한 이차원 배열 탐색.
2. 유니온 파인드
3. 해시 테이블(딕셔너리, 셋)

접근한 방법

1. 지도에 각 문명의 정보를 표시한다.
2. set에 '통합되지 않은 문명 번호'를 기입한다.
3. dict에 '각 문명별 발상지' 를 기입한다. key는 문명 번호, value는 그 문명 발상지의 좌표.

정보를 입력받은 뒤에 이차원 배열을 탐색한다. 다른 문명과 인접할 때마다 Union연산을 수행한다. 문명이 모두 통합되었다면 탐색을 종료한다. 

+ 각 문명이 통합될 때, dict에서 '문명별 발상지' 의 좌표 또한 업데이트한다. 이렇게 하면 타일에 '아직 통합되지 않은 문명 번호'가 남아있다 하더라도 그 숫자들을 '통합된 문명 번호' 취급할 수 있다.  

 

개선 가능한 점

1.  4 방향 탐색 부분 코드가 계속 반복된다. 해당 부분을 함수화했다면 훨씬 코드가 간결해졌을 것이다.
2. origin_set의 길이를 참조하는 대신, 문명의 통합 여부를 flag list와 정수(ex: independent_civs)로 남은 문명의 갯수를 세었다면 훨씬 실행시간을 줄일 수 있었을 것.
3. 코드의 번잡함. 유사한 실행시간에 코드 길이가 절반정도 되는 풀이를 봤다. 

어려웠던 점 

1. 구현해야 할 양이 많은 편이었다.

'상어 초등학교'를 풀이할 때에도 비슷한 풀이를 활용했다. 

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

21608번: 상어 초등학교

https://programmer-565.tistory.com/22

21608. 상어 초등학교 - 구현, 시뮬레이션, counter sort, 해시 테이블. 파이썬

느낀 점

1. 문제를 꼼꼼하게 읽고 전체 문제를 작은 단위로 분할한다. 

풀이했을 당시의 백준 티어

2021-10-18, 골드 3

 

실행시간, 메모리, 언어

2388ms, 263556kb, Pypy3 - 100점

2021-11-03 현재 실행시간 1등

 

6888ms, 95924kb, Python3- 54점

from sys import stdin
from collections import deque

# 1. 유니온 함수.
def union(a_row, a_col, b_row, b_col):
    # 1) 예외 처리
    origin_a = find(a_row, a_col)
    origin_b = find(b_row, b_col)

    # 만약 a 지점과 b 지점의 조상이 같다면
    if origin_b == origin_a:
        return  # 연산하지 않음.

    # 2) 연산
    # (1) b가 통합된 문명일 때
    if origin_b not in origin_set:
        # b의 좌표에 a의 조상 문명 번호를 지도에 기입.
        MAP[b_row][b_col] = origin_a
        return

    # (2) a가 통합된 문명일 때
    if origin_a not in origin_set:
        # a의 좌표에 b의 조상 문명 번호를 지도에 기입.
        MAP[a_row][a_col] = origin_b
        return

    # (3) a와 b 모두가 존재할 때
    # 문명 번호가 더 작은 것을 우선순위로 통합.
    if origin_a < origin_b:
        MAP[b_row][b_col] = origin_a
        origin_set.remove(origin_b)
        origin_location[origin_b] = origin_location[origin_a]
        return

    else:
        MAP[a_row][a_col] = origin_b
        origin_set.remove(origin_a)
        origin_location[origin_a] = origin_location[origin_b]
        return


# 2. find 함수
def find(row, col):

    # 1) 선언
    # 현재 조상을 확인하고 싶은 값.
    x = MAP[row][col]

    # 2) 연산
    # (1) 예외처리: 현재 좌표값이 '근원지' 중 하나일 때
    if x in origin_set:
        return x    # 그대로 리턴

    # (2) 부모 정보 업데이트
    # a. origin_location 딕셔너리에서 x값의 '근원지' 값을 가져옴
    x_row, x_col = origin_location[x]

    # b. find
    origin = find(x_row, x_col)

    # c. 조상 정보 갱신
    MAP[row][col] = origin      # 조상 정보를 갱신.

    # 3) 반환
    return origin


# 델타를 이용한 2차원 배열 탐색.
DX = (0, 0, -1, 1)  # 상, 하, 좌, 우
DY = (-1, 1, 0, 0)  # 상, 하, 좌, 우

# 1. 입력
N, K = map(int, stdin.readline().split())

# 1-1. 추가 입력을 위한 선언
# 1) 각 좌표별 문명 정보를 기록하는 2차원 배열
MAP = [[0] * N for _ in range(N)]

# 2) key: 문명 번호, value: 문명 번호의 발상지
origin_location = dict()

# 3) 아직 통합되지 않은 발상지 번호들의 집합.
origin_set = set(range(1, K + 1))


# 2. 선언
civ_que = deque()   # 문명들 정보를 저장하는 que
next_que = deque()  # BFS 연산을 위한 que (2)

# 1-2. 문명 발상지 정보 입력.
# 문명 번호 1번부터 K 번 까지
for civilization in range(1, K + 1):
    # 1) 입력
    # 행, 열 좌표를 입력받아
    row, col = map(int, stdin.readline().split())
    row -= 1
    col -= 1

    # 2) 연산
    # (1) 지도에 배치
    MAP[row][col] = civilization

    # (2) 딕셔너리에 기입
    origin_location[civilization] = (row, col)

    # (3) 큐에 기입
    civ_que.append((row, col))

# 1-3. 문명 발상지 상쇄 .
for civ in civ_que:
    row, col = civ

    # 4방향을 순회하며
    for direction in range(4):
        next_row = row + DY[direction]
        next_col = col + DX[direction]

        # 인접 문명이 있을 경우
        if N > next_row >= 0 and N > next_col >= 0\
                and MAP[next_row][next_col]:
            # 문명 통합.
            union(row, col, next_row, next_col)

# 2. 연산
result = 0

# 종료조건:
# 문명들이 모두 1개로 통합되었을 때
while len(origin_set) != 1:
    result += 1

    # BFS 연산
    while civ_que:
        # 큐에 있는 모든 문명 좌표를 순회.
        row, col = civ_que.popleft()

        # 현재 좌표에 인접한 4 방향을 순회하며
        for direction in range(4):
            next_row = row + DY[direction]
            next_col = col + DX[direction]

            # 인덱스 값이 정상이고
            if N > next_row >= 0 and N > next_col >= 0:

                # 1) 문명이 전파되지 않은 지역이라면
                if not MAP[next_row][next_col]:
                    # 문명을 전파
                    MAP[next_row][next_col] = MAP[row][col]
                    # 다음 큐에 입력
                    next_que.append((next_row, next_col))

                    # (1) 문명 전파 후 옆에 다른 문명이 있는지 다시 확인.
                    for next_direction in range(4):
                        nnext_row = next_row + DY[next_direction]
                        nnext_col = next_col + DX[next_direction]

                        # 4 방향 순회 후
                        if N > nnext_row >= 0 and N > nnext_col >= 0\
                            and MAP[nnext_row][nnext_col]\
                                and MAP[nnext_row][nnext_col] != MAP[next_row][next_col]:
                            # 인접한 문명을 다시 통합.
                            union(next_row, next_col, nnext_row, nnext_col)

                # 2) 문명이 전파되었으며 아직 통합되지 않았다면
                elif MAP[next_row][next_col] != MAP[row][col]:
                    union(row, col, next_row, next_col)
    # 현재 큐-다음 큐 교체 연산.
    next_que, civ_que = civ_que, next_que

# 4 .출력.
print(result)