[구름톤 챌린지 #13] 발전기 (2)

문제13. 발전기 (2)

구름LEVEL

---

---

문제 해결 방법

오늘 구름톤 챌린지 문제는 어제와 사실상 같은 문제이다. 다만 어제는 1과 0 두 가지 경우로만 고려했다면, 오늘 문제는 1~30의 임의의 수를 고려해야하는 문제이다. 문제를 복잡하게 설명해서 이해하기 어렵지만, 같은 유형 건물이 k 개 이상 붙어있는 곳은 단지가 되고, 가장 많은 단지가 형성된 건물의 유형을 구하면 되는, 사실은 간단한 요구사항을 가진 문제이다.

 

어제와 같이 BFS를 적용하되 어제는 count를 설치할 발전소의 숫자로 하였다면, 오늘은 k개 이상의 건물이 서로 인접해 있는지를 판단하기 위해, 인접한 건물의 수를 세기 위한 변수로 count를 사용한다. 한편 건물의 유형을 30개로 제한해 두었으므로 각 건물 유형 당 단지의 개수는 길이가 30인 리스트(num_of_complex)로 관리해도 큰 부담이 안된다.

 

나머지는 어제와 같다. 모든 구역을 탐색하되, 아직 탐색되지 않은 곳이라면 그 주변 영역을 같이 탐색해서 단지가 형성되는지를 확인한다. 단지가 형성되었다면 num_of_complex의 값을 1 올리고, 최종적으로 num_of_complex에서 최댓값을 갖는 인덱스를 출력해주면 된다.

 

위 내용을 코드로 구현하면 아래와 같다.

import sys
from collections import deque

n, k = map(int, sys.stdin.readline().split())
dq = deque()

# 인덱스가 넘치는 것을 막기 위해 의미없는 데이터 한줄 늘려줌
arr = [(list(map(int, sys.stdin.readline().split())) + [0]) for i in range(n)]
arr.append([0 for i in range(n + 1)])

dr = [1, -1, 0, 0]
dc = [0, 0, -1, 1]

num_of_complex = [0 for i in range(31)]

for r in range(n):
    for c in range(n):
        # 0이라면 상관 없음(이미 방문한 곳)
        if arr[r][c] == 0:
            continue
        building_type = arr[r][c]
        count = 0

        dq.append((r, c))
        while dq:
            # 큐에서 하나 꺼내오고
            pop_r, pop_c = dq.popleft()
            # 꺼내온게 빌딩 타입과 같다면(같은 단지라면) 0으로 바꾸고 거기서 다시 상하좌우 뻗어
            if arr[pop_r][pop_c] == building_type:
                count += 1
                arr[pop_r][pop_c] = 0
                for i in range(4):
                    dq.append((pop_r + dr[i], pop_c + dc[i]))

        if count >= k:
            num_of_complex[building_type] += 1

max_complex = 0
for i in range(len(num_of_complex)):
    if num_of_complex[i] >= num_of_complex[max_complex]:
        max_complex = i

print(max_complex)