[백준] 2667번:단지번호붙이기 (python 파이썬)

문제

www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

풀이

dfs로 풀었다.

현재 가리키는 좌표가 i,j 라고 할 때, arr[i][j] 가 1이면 방문 표시로 0으로 바꿔주고, i,j 를 기준으로 상하좌우에 1인 곳이 있는지 확인한다.

소스코드

import sys
input = sys.stdin.readline

def dfs(x, y, cnt):
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    arr[x][y]=0
    for i in range(4):
        nowx, nowy = x+dx[i], y+dy[i]
        if nowx<0 or nowy<0 or nowx>=n or nowy>=n or not arr[nowx][nowy]:
            continue
        cnt = dfs(nowx, nowy, cnt+1)
    return cnt

n = int(input())
arr = [list(map(int, list(input().strip()))) for _ in range(n)]
cnt = 0
ans = []
for i in range(n):
    for j in range(n):
        if arr[i][j] == 1:
            ans.append(dfs(i, j, 1))
print(len(ans))
for i in sorted(ans):
    print(i)