[구름톤 챌린지] 3주차 13일차 발전기 (2)

 

 

문제

---

구름 심시티를 하고 있는 플레이어는 한 변의 길이가 $N$인 정사각형 모양의 마을 $M$을 만들고 있다. 마을의 모든 칸에는 건물이 하나씩 있고, $r$번째 행, $c$번째 열에 해당하는 칸에는 정수 $M_{r, c}$가 적혀 있다. $M_{r, c}$는 해당 칸에 있는 건물의 유형의 번호를 의미한다.

건물의 유형이 동일하면서, 서로 상하좌우 인접한 칸에 위치한 건물끼리는 서로 전력을 공유할 수 있다. 전력을 공유할 수 있는 관계에 속한 건물의 개수가 $K$개 이상이면 이를 단지라고 한다.

플레이어는 발전기를 설치해 각 단지에 전력을 공급하고자 한다. 하지만 비용 문제로 인해 단 하나의 발전기만 설치할 수 있다. 발전기는 특정 건물 유형 하나에 해당하는 모든 단지에 전력을 공급할 수 있다. 그래서 플레이어는 가장 많은 단지가 있는 건물 유형에 전력을 공급할 것이다. 만약 그러한 건물 유형이 여러 개라면, $M_{r, c}$가 더 큰 건물 유형에 전력을 공급한다.

플레이어가 전력을 공급해야 할 건물의 유형 번호를 구해보자.

입력

---

첫째 줄에 마을의 크기 $N$과 단지의 기준 $K$가 공백을 두고 주어진다.
다음 $N$개의 줄에는 마을의 상태를 나타내는 $N$개의 숫자가 공백을 두고 주어진다. $r$번째 줄에서 $c$번째로 주어지는 값이 $M_{r, c}$에 해당한다.

 

 

• $1 \leq N \leq 1 \ 000$
• $1 \leq K \leq 50$
• $1 \leq M_{r, c} \leq 30$
• 최소 하나 이상의 단지가 있는 입력만 주어진다.
• 주어지는 모든 수는 정수이다.

출력

---

플레이어가 전력을 공급해야 할 건물의 유형 번호를 출력한다.

 

---

문제 접근 방식

---

어제 해결했던 발전기 문제와 거의 유사한 연결요소 찾기 문제다. BFS또는 DFS로 해결할 수 있다.

 

나의 경우 BFS로 구현했다.

 

연결 요소의 개수를 반환하는 BFS함수를 구현했다.

 

이후 연결 요소의 개수가 $K$개 보다 크다면 단지로 간주하고, 해당하는 단지 번호에 단지 개수를 $+1$ 해주면 된다.

 

이후 문제에서 주어진 것 처럼 가장 많은 단지를 가진 단지 번호를 출력하면 된다.

 

---

정답 코드

---

# 발전기 (2)
import sys
input = sys.stdin.readline
from collections import deque

N, K = map(int, input().rstrip().split())
M = [list(map(int, input().rstrip().split())) for _ in range(N)]
dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]
def BFS(r, c):
    queue = deque()
    queue.append((r, c))
    k = M[r][c]
    M[r][c] = 0
    total = 1
    while queue:
        nr, nc = queue.popleft()
        for i in range(4):
            nnr, nnc = nr+dr[i], nc+dc[i]
            if 0 <= nnr < N and 0 <= nnc < N and M[nnr][nnc] == k:
                M[nnr][nnc] = 0
                queue.append((nnr, nnc))
                total += 1
    return total

danji = dict()
for r in range(N):
    for c in range(N):
        if M[r][c]:
            danji_num = M[r][c]
            building_cnt = BFS(r, c)
            if building_cnt >= K:
                if danji_num in danji:
                    danji[danji_num] += 1
                else:
                    danji[danji_num] = 1
print(sorted(danji.items(), key = lambda tpl: (tpl[1], tpl[0]))[-1][0])

 

---

특별히 배운 점

---

기존의 코드를 살짝 고쳐서 AC를 받았다. DFS로도 풀면 좋은 연습이 될 것 같다.