[ 구름톤 챌린지 ] 20일차 미션 - 연결 요소 제거하기

20일차 오픈런

구름톤 챌린지가 20일차를 끝으로 마무리 되었습니다! 20일차 동안 문제를 풀면서 느꼈던 점은, 코딩테스트를 준비하는 사람들에게 교육적인 문제가 많이 출제되어 유익하다는 점과 문제 하나하나가 재밌어서 매일 참여해야겠다는 흥미를 얻을 수 있었다는 점입니다. 한편으로는 기간이 더 길게 진행되어 더 많은 문제를 풀어볼 수 있다면 좋겠다는 생각도 들었지만, 본인의 Problem Solving 역량을 체크하는데 적정한 문제와 기간이였다고 생각합니다. 

https://level.goorm.io/l/challenge/goormthon-challenge

구름LEVEL

 

문제

입력 / 출력

풀이 과정

특정 칸에 알파벳 대문자를 쓸 때는 그 칸이 비어있음이 보장되므로, 알파벳 대문자를 쓸 때마다 그 대문자와 연결된 요소들의 개수가 K 를 넘는지 확인하고, 만약 요소들이 K 개를 넘는다면 그때 비워주는 방식으로 BFS 를 사용하여 풀이했다.

처음에는 크기가 K 이상인 연결 요소가 존재하지 않고, 배열의 크기 제한도 작아서 쿼리가 들어올 때마다 탐색을 수행해도 수월하게 풀이할 수 있었다.

import sys
from collections import deque
input = sys.stdin.readline

n, k, q = map(int, input().rstrip().split())
maps = [list(input().rstrip()) for _ in range(n)]

row = [-1, 1, 0, 0]
col = [0, 0, -1, 1]

for _ in range(q):
	y, x, alpha = input().rstrip().split()
	y = int(y) - 1; x = int(x) - 1
	
	maps[y][x] = alpha
	
	cnt = 1
	queue = deque()
	queue.append((y, x))
	visited = [[0 for _ in range(n)] for _ in range(n)]
	visited[y][x] = 1
	order = [(y, x)]
	
	while queue:
		c_y, c_x = queue.popleft()
		
		for d in range(4):
			ny = c_y + row[d]
			nx = c_x + col[d]
			
			if 0 <= ny < n and 0 <= nx < n and visited[ny][nx] == 0 and maps[ny][nx] == alpha:
				visited[ny][nx] = 1
				cnt += 1
				queue.append((ny, nx))
				order.append((ny, nx))
	
	if cnt >= k:
		for cy, cx in order:
			maps[cy][cx] = '.'

for i in range(n):
	print(''.join(maps[i]))