[구름톤 챌린지 #20] 연결 요소 제거하기

문제20. 연결 요소 제거하기

구름LEVEL

---

---

문제 해결 방법

4주 동안의 구름톤 챌린지의 막을 내리는 문제이다. 지금까지의 문제들을 잘 풀었다면, 오늘 문제도 어렵지 않게 풀 수 있는 DFS/BFS 문제였다.

 

상하좌우 4가지 방향에 있는 칸들에 대해, 입력받은 p와 같은 경우에만 BFS/DFS를 이용해 파급이 되도록 만들면 된다. 파급이 되는 동안 방문하지 않은 곳이라면 count 를 올려주고, 방문한 곳이라면 해당 칸은 스킵한다. 파급이 끝나면 count의 개수에 따라 "."으로 해당 칸을 바꿀지를 결정하면 된다.

 

위 내용을 코드로 구현하면 아래와 같다.

import sys
from collections import deque

n,k,q = map(int, sys.stdin.readline().split())

#범위 조건을 따로 체크하지 않아도 되도록 테두리를 "."으로 둘러주었음
arr = [["." for i in range(n+2)]] + [(["."] + list(sys.stdin.readline().rstrip()) + ["."]) for i in range(n)] + [["." for i in range(n+2)]]

dy = [-1,1,0,0]
dx = [0,0,-1,1]

dq = deque()
for i in range(q):
    y,x,p = sys.stdin.readline().split()
    y = int(y)
    x = int(x)

    visited = set()
    visited.add((y,x))
    dq.append((y,x))
    arr[y][x] = p
    count = 1

    while dq:
        popped_y, popped_x = dq.popleft()
        for direction in range(4):
            next_y = popped_y + dy[direction]
            next_x = popped_x + dx[direction]

            if arr[next_y][next_x] != p or  (next_y, next_x) in visited:
                continue

            count+=1
            visited.add((next_y, next_x))
            dq.append((next_y, next_x))

    # 연결요소가 k개 이상이면 연결된 요소들을(visited의 요소들을) .으로 변경
    if count >= k:
        for connected_y, connected_x in visited:
            arr[connected_y][connected_x] = "."


for i in range(1, n+1):
    for j in range(1, n + 1):
        print(arr[i][j], end="")
    print ("")

---

구름톤 챌린지 간단 후기

4주의 시간 동안, 구름톤 챌린지가 공개되는 오전 10시가 되자마자 습관처럼 컴퓨터 앞에 앉아 구름톤 챌린지 문제를 풀었고, 평균적으로 30분 ~ 1시간의 문제풀이 시간을 가진 후에 하루 일과를 시작하게 되었다. 난이도가 너무 낮다고 생각했던 첫 주의 구현 문제부터 시작하여, 익숙해져있지 않은 4주차의 그래프 탐색에 이르기까지 하루도 빠짐 없이 알고리즘 문제를 풀면서, 성장의 관성인 꾸준히 하는 습관을 얻어간 것 같다는 생각을 하게 되었다.

 

알고리즘에 대한 자신감도 많이 늘었다. 기존의 나는 DFS/BFS나 그래프 탐색은 어려운 것이라고만 생각을 하고, 이 알고리즘들의 공부를 미루고 DP나 구현 문제 위주로 많이 풀었었다. 이번 구름톤 챌린지를 기회 삼아 내가 약한 알고리즘들에 도전하는 계기가 되었고 결과적으로 도전에 성공하여, 앞으로 만날 다른 어려운 알고리즘들도 풀어낼 수 있을 것이라는 자신감을 많이 얻었다.

 

앞으로 중요한 것은, 챌린지가 끝났다고 성장도 따라서 멈추지 않도록 끊임없이 노력하는 것이다. 얻어낸 습관과 자신감을 바탕으로 새로운 알고리즘, 어려운 문제들에 계속해서 도전하여 웬만한 알고리즘 문제를 어렵지 않게 풀어낼 수 있는 개발자로 성장하고 싶다.