[구름톤 챌린지] 4주차 20일차 연결 요소 제거하기

문제

---

$N \times N$ 크기의 2차원 배열이 있다. 2차원 배열의 $i$행 $j$열에 해당하는 칸은 $(i, j)$로 나타낸다. 처음에 이 배열의 각 칸에는 알파벳 대문자 또는 . 문자가 하나 적혀 있다.

상하좌우로 인접한 두 칸에 같은 문자가 적혀있는 경우, 두 칸은 연결되어 있다고 한다. 서로 연결된 칸들의 집합을 연결 요소라고 하고, 연결 요소의 크기는 그 연결 요소에 포함된 칸들의 개수와 같다. 

구름이는 아래 작업을 $Q$번 수행하려고 한다.

 

 

1. $(y_i, x_i)$ 칸을 고른 뒤, 그 칸에 알파벳 대문자 $d_i$를 쓴다. 구름이가 고른 칸은 . 문자가 적힌 칸임이 보장된다.
2. 배열에 존재하는 모든 연결 요소의 크기를 계산한다. 만약 크기가 $K$ 이상인 연결 요소가 존재한다면, 그 연결 요소에 포함된 모든 칸에 적힌 문자를 지운다.

모든 작업을 수행한 뒤에, 배열에 적혀있는 문자를 구해보자.

입력

---

첫째 줄에 배열의 크기 $N$, 연결 요소를 지울 기준 $K$, 그리고 구름이가 문자를 적을 횟수 $Q$가 공백을 두고 주어진다.
다음 $N$개의 줄에는 $N$개의 문자가 주어진다. 주어지는 문자는 . 또는 알파벳 대문자 중 하나이며, . 문자는 처음에 배열의 칸이 비어있음을 의미한다. $r$번째 줄에서 $c$번째로 주어지는 문자는 $(r, c)$ 칸에 대한 정보이다.
다음 $Q$개의 줄에는 두 정수 $y_i, x_i$와 알파벳 대문자 $d_i$가 공백을 두고 주어진다. 구름이가 $(y_i, x_i)$ 칸에 $d_i$ 문자를 적었음을 의미한다.

 

 

• $3 \leq N \leq 50$
• $2 \leq K \leq 50$
• $1 \leq Q \leq 1 \ 000$
• $1 \leq x_i, y_i \leq N$
• 처음에는 크기가 $K$ 이상인 연결 요소가 존재하지 않는다.
• 구름이가 문자를 적을 칸은 비어있음이 보장된다.
• $d_i$는 알파벳 대문자이다.

출력

---

구름이가 $Q$개의 작업을 모두 수행한 뒤, 마지막에 배열에 적혀있는 문자를 $N$개의 줄에 걸쳐 출력한다. 아무 문자도 적혀있지 않은 칸은 . 문자를 대신 출력한다.

 

---

문제 접근 방식

---

연결 요소 탐색은 BFS로 진행했다.

 

각 연결 요소를 다른 색깔로 칠하는 방식을 택했는데, 이때 연결요소의 크기가 $K$이상이 되는 색깔을 $\textrm{over_K}$라는 셋에 담아주었다.

 

이후 그래프의 각 요소를 탐색하며 칠해진 색깔이 만약 $\textrm{over_K}$에 있다면 빈 문자 $.$로 바꿔주었다.

 

총 시간 복잡도는 $O(QN^2 \textrm{BFS_time})$에 해당한다고 생각하여 구현하였다.

 

---

정답 코드

---

# 연결 요소 제거하기
import sys
input = sys.stdin.readline
from collections import deque

N, K, Q = map(int, input().rstrip().split())
graph = [list(input().rstrip()) for _ in range(N)]

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

def query(y, x, d):
    graph[y-1][x-1] = d
    visited = [[0 for _ in range(N)] for _ in range(N)]
    color = 1
    over_K = set()
    for r in range(N):
        for c in range(N):
            if visited[r][c] == 0:
                queue = deque()
                queue.append((r, c))
                visited[r][c] = color
                cnt = 0
                while queue:
                    R, C = queue.popleft()
                    cnt += 1
                    for i in range(4):
                        nr, nc = R+dr[i], C+dc[i]
                        if 0 <= nr < N and 0 <= nc < N and visited[nr][nc] == 0 and graph[nr][nc] == graph[r][c]:
                            visited[nr][nc] = color
                            queue.append((nr, nc))
                if cnt >= K:
                    over_K.add(color)
                color += 1
    for r in range(N):
        for c in range(N):
            if visited[r][c] in over_K:
                graph[r][c] = '.'

for _ in range(Q):
    y, x, d = input().rstrip().split()
    y, x = int(y), int(x)
    query(y, x, d)

for row in range(N):
    print(''.join(graph[row]))

 

---

특별히 배운 점

---

오늘로써 구름톤 챌린지가 마무리 되었다.

 

4주라는 시간 동안 알고리즘의 기초를 다질 수 있는 문제를 풀 수 있어서 좋았다.

 

다만, 문자열이나 기하 혹은 스택이나 우선순위 큐 같은 자료 구조 활용문제를 다루지 않아서 아쉬웠다.

 

만약 다음에도 이런 이벤트가 생긴다면 다양한 문제를 다루면 좋겠다는 아쉬움이 있다.

 

이런 이벤트를 연 구름 관계자 분께 감사의 말씀을 전하고 싶다.