[구름톤 챌린지 WEEK 4 - 그래프 탐색] DAY 20. 연결 요소 제거하기

한 달간 진행됐던 구름톤 챌린지 마지막 날이다! 위 사진은 4주간 모은 캐릭터 아이템 🤣

그동안 완벽히 이해하지 못한 알고리즘 문제들도 있는데 9월 달 내로 다시 리뷰하며 풀어보는 것을 목표로 잡았다.

결과적으로 20개 블록을 모두 모았고, 시작하기 전의 내 알고리즘 실력과 지금을 비교하면 배우면서 더 성장했음을 느낀다!

 

DAY 20. 연결 요소 제거하기

def f(y, x, d):
    graph[y][x] = d
    stack = [(y, x)]
    
    # 조건을 만족하는 연결 요소이면, 포함되는 모든 칸을 '.'으로 바꾸기 위해 해당 위치 저장할 집합 선언
    # + 방문 체크
    visited = set()
    
    while stack:
        ey, ex = stack.pop()
        
        if (ey, ex) in visited:
            continue
            
        # 방문 처리
        visited.add((ey, ex))
        
        # 상하좌우 탐색
        for i in range(4):
            ny, nx = ey + direction[i][0], ex + direction[i][1]
            
        # 범위를 벗어나거나, 인접한 칸의 다른 문자가 올 경우 건너뜀
        if ny in (-1, N) or nx in (-1, N) or graph[ny][nx] != graph[y][x]:
            continue
                
        stack.append((ny, nx))
            
    # 방문한 칸이 K개 이상이면 방문했던 모든 칸을 "."로 바꿔준다
    if len(visited) >= K:
        for y, x in visited:
            graph[y][x] = "."
				
direction = [[-1, 0], [1, 0], [0, -1], [0, 1]]

# 배열의 크기, 연결 요소 지울 기준, 문자 적을 횟수
N, K, Q = map(int, input().split())
graph = [list(input()) for _ in range(N)]

for _ in range(Q):
    y, x, d = input().split()
    f(int(y) - 1, int(x) - 1, d)
	
for c in graph:
    print(''.join(c))

입력받은 칸에 d 문자를 적고, 그 상하좌우를 돌며 인접한 문자(연결 요소)를 세는 부분에서 어려움을 겪었는데,

범위를 벗어나지 않고 + 인접 칸에 같은 문자가 오는 칸을 visited에 방문 처리를 해주고

visited 개수가 K를 넘는다면 visited에 들어있는 좌표 모두 "."로 바꿔주면 되었다.