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

www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

정답률이 꽤 낮은 문제이지만, dfs/bfs를 잘 이용하면 그리 어렵지않은 문제이다

from collections import deque
import sys

def DFS(i, j):
    que = deque()

    if i < 0 or i >= n or j < 0 or j >= n:
        return None

    else:
        cnt = 0
        if List[i][j] == 1:
            que.append([i, j])
            List[i][j] = 0

            while que:
                p = que.popleft()
                xx = p[0]
                yy = p[1]
                cnt += 1
                for k in range(4):
                    x = dx[k]
                    y = dy[k]

                    if xx + x < 0 or xx + x >= n or yy + y < 0 or yy + y >= n:
                        continue

                    else:
                        if List[xx + x][yy + y] == 1:
                            que.append([xx + x, yy + y])
                            List[xx + x][yy + y] = 0
            return cnt

        else:
            return None

n = int(sys.stdin.readline().rstrip())
List = []
result = []
for i in range(n):
    List.append(list(map(int, sys.stdin.readline().rstrip())))

# 상,하,좌,우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]


p_cnt = 0  # 단지 내 아파트
for i in range(n):
    for j in range(n):
        k=DFS(i,j)
        if k == None:
            continue
        else:
            result.append(k)
            p_cnt += 1

print(p_cnt)
result=sorted(result)
for i in result:
    print(i)