[Boj] 단지번호붙이기 2667(python)

문제링크 : https://www.acmicpc.net/problem/2667

입력의 첫 줄에는 행의 개수 N이 주어지며. 그 다음 줄부터 각 행에 관한 정보가 입력됨

집이 있는 곳은 1로 나타나기 때문에, dy와 dx를 통해 DFS를 사용하면 구현 가능

집이 있는 곳에서 DFS함수를 실행하며, 스택에 좌표 정보를 넣고 상하좌우 검사 후 스택에 넣는 구조

필자는 보통 DFS를 사용할 때 10026에서 사용된 함수 혹은 이번 문제에서 사용한 것처럼 구현함

이때, 주의할 점은 sys.setrecursionlimit(10**8) 안할시 오류가 생길 수 있음

결국, DFS나 BFS로 풀 수 있는 문제이며, 필자는 DFS를 선택

import sys
sys.setrecursionlimit(10**8)

def DFS(row, col):
    global tmp_answer
    to_visits = [[row, col]]
    matrix[row][col] = 0
    while to_visits:
        current_row, current_col = to_visits.pop()
        for i in range(4):
            next_row, next_col = current_row + dx[i], current_col + dy[i]
            if 0<=next_row < n and 0<= next_col < n and matrix[next_row][next_col] == 1:
                to_visits.append([next_row, next_col])
                tmp_answer += 1
                matrix[next_row][next_col] = 0


n = int(input())
matrix = []
for _ in range(n):
    tmp = list(map(int, input()))
    matrix.append(tmp)

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
answer = 0
answer_list = []
for row in range(n):
    for col in range(n):
        tmp_answer = 1
        if matrix[row][col] == 1:
            DFS(row, col)
            answer_list.append(tmp_answer)
            answer += 1
answer_list.sort()
print(answer)
for ans in answer_list:
    print(ans)