[BOJ 2667] 단지 번호 붙이기(Python)

문제링크

단지 번호 붙이기

풀이 전 계획 및 생각

지도에 있는 모든 점들을 시작점으로 하면서 각 점들에서 dfs를 해보자는 생각을 했다.
반복문말고 recursion을 이용해서 dfs를 구현해보기로 결정했다.
재귀의 스택 깊이가 너무 깊어지면 안되니까 sys.setrecursionlimit를 걸어줘서 해결했다.
그리고 단지를 구분해야하기 때문에 단지의 갯수를 count하는 변수와 각 단지에 있는 집의 수를 저장하는 ans 배열을 따로 만들어서 저장했다. 최종 결과가 각 단지내 집의 수를 오름차순으로 정렬해서 출력하면 되는 문제였기 때문에 저장을 할 때는 (단지 번호, 집의 수)와 같은 튜플 형식이 아닌 집의 수만 저장했다.

풀이

import sys
sys.setrecursionlimit(100000)


def dfs(x,y,count):
    visited[x][y] = True
    count += 1
    directions = [(-1,0),(1,0),(0,-1),(0,1)]
    for dx, dy in directions:
        nx, ny = x+dx, y+dy
        if nx<0 or nx>=n or ny<0 or ny>=n:
            continue
        if array[nx][ny] and not visited[nx][ny]:
            count = dfs(nx,ny,count)
    return count
n = int(input())
array = [[0]*n for _ in range(n)]
visited = [[False] * n for _ in range(n)]
for i in range(n):
    string = input()
    for j in range(n):
        array[i][j] = int(string[j])
    result = 0
ans = list()
for i in range(n):
    for j in range(n):
        if array[i][j] and not visited[i][j]:
            ans.append(dfs(i,j,0))
            result += 1
ans.sort()
print(result)
for i in range(result):
    print(ans[i])

풀이하면서 막혔던 점과 고민했던 점

제일 고민했던 것은 각 단지들을 전부 탐색할 경우에 이미 다녀간 단지들을 살펴보는 것을 어떻게 해결할 것인지였다.

해결 방법은 visited 배열을 2차원으로 설정하고 dfs를 실행하기 전에 지금 보는 시작 노드를 이전에 방문했는지 보고, 이전에 방문하지않은 노드들만 방문하도록 구현해서 불필요한 연산을 줄일 수 있었다.

풀이 후 알게된 개념과 소감

visited 배열도 필요에 맞게 바꿔가며 구현해야한다는 것을 배웠다.