[Python] 백준 2667번. 단지번호 붙이기

https://www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

 

풀이

• 입력받은 배열에 1이 있다면 dfs 함수를 호출합니다.
• x,y의 인덱스가 n보다 크거나 0보다 작아지면 배열 범위를 벗어나기 때문에 return을 합니다.
• x,y 좌표에 1이 있다면 count을 증가시킵니다. -> 1의 갯수를 셉니다.
• 위,아래,오른쪽,왼쪽을 확인하며 1이 있는지 확인합니다.
• 1이 있다면 다시 dfs을 호출합니다.

import sys

input = sys.stdin.readline

N = int(input())
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

result = []
count = 0
def dfs(x, y):
    global count

    if x < 0 or x >= N or y < 0 or y >= N:
        return

    if maps[x][y] == '1':
        count += 1
        maps[x][y] = '0'
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            dfs(nx, ny)

maps = list()
for i in range(N):
   maps.append(list(input()))

for i in range(N):
    for j in range(N):
        if maps[i][j] == '1':
            dfs(i, j)
            result.append(count)
            count = 0

result.sort()
print(len(result))
for k in result:
    print(k)