구름톤 챌린지 Week 4 - Day 20

https://level.goorm.io/exam/195702/연결-요소-제거하/quiz/1

"배열에 존재하는 모든 연결 요소의 크기를 계산한다"라고 하는 2번 조건은 함정에 가깝다.

"처음에는 크기가 K 이상인 연결 요소가 존재하지 않는다"와 "문자를 적을 칸은 비어있음이 보장된다."

이 두 조건에 따르면, 입력이 주어졌을 때만 그 부분에 대해서 DFS나 BFS를 수행하면 된다.

 

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


def BFS(x, y, value, graph):
    queue = deque([(x, y)])
    
    footprint = [(x, y)]
    visited = [[0] * length for _ in range(length)]
    visited[x][y] = 1
    
    while queue:
        x, y = queue.popleft()
        
        for dx, dy in dxy:
            nx = x + dx
            ny = y + dy
            
            if 0 <= nx < length and 0 <= ny < length\
            and visited[nx][ny] == 0 and graph[nx][ny] == value:
                visited[nx][ny] = 1
                queue.append((nx, ny))
                footprint.append((nx, ny))
                
    if len(footprint) >= K:        
        for cx, cy in footprint:
            graph[cx][cy] = "."
        
    return


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

# UP, DN, LFT, RGT
dxy = [(-1, 0), (1, 0), (0, -1), (0, 1)]

for _ in range(question):
    changeX, changeY, alphabet = map(str, input().split())
    graph[int(changeX)-1][int(changeY)-1] = alphabet
    BFS(int(changeX)-1, int(changeY)-1, alphabet, graph)
    
for line in graph:
    print(''.join(line))

다른 BFS와 코드가 유사하여 특별하게 설명할 부분은 없다.

다만 dx, dy로 선언한 방향 list는 dxy로 index가 아니라 값으로 직접 계산할 수 있게 수정했다.

아무래도 index로 접근하는 것보다는 값을 직접 순회하는 것이 빠르기 때문이다.

 

for _ in range(question):
    changeX, changeY, alphabet = map(str, input().split())
    changeX = int(chagneX) - 1
    changeY = int(changeY) - 1
    
    graph[changeX][intchangeY] = alphabet
    BFS(intchangeX, changeY, alphabet, graph)

[x][y]에는 이미 온점(.)이 있을 테니, alphabet으로 바꿔준다.

그리고 해당 위치에서부터 BFS를 수행한다.

 

 

def BFS(x, y, value, graph):
    ''' 초기화 코드 작성 '''
    
    footprint = [(x, y)]
    
    ''' BFS 코드 작성 '''
                
    if len(footprint) >= K:        
        for cx, cy in footprint:
            graph[cx][cy] = "."
        
    return

footprint 객체는 BFS로 탐색한 위치를 저장하는 list다.

만약 footprint의 개수가 K보다 크거나 같으면 footprint에 해당하는 모든 좌표를 '."으로 바꾼다.