백준 2667 단지번호 붙이기 파이썬

문제

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

문제 요약

1끼리 상하좌우로 연결 → 단지

단지 수 출력하고, 각 단지 속하는 집 수 오름차순 출력

슈도 코드

1. 특정 지점 상, 하, 좌, 우 살피기

2. 주변 지점 중 값이 1이면서 방문하지 않은 지점 있으면 해당 지점 방문방문했을 때 값을 0으로 바꾸고 카운트 +1

    각 단지별로 카운트 한 값을 배열에 저장한다.

    방문한 지점에서 다시 상하좌우 살피며 방문 반복

 

3. 1, 2번의 과정을 반복하며, 방문하지 않은 지점을 방문한다.

4. 각 단지별 카운트를 오름차순으로 정렬한다.

제출코드

import sys

n = int(sys.stdin.readline())
result = []
graph = []
ind = 0

for i in range(n):
    graph.append(list(map(int, sys.stdin.readline().rstrip())))
cnt = 0

def dfs(x, y):
    global cnt
    if x <= -1 or x >= n or y <= -1 or y >= n:
        return cnt
    if graph[x][y] == 1:
        graph[x][y] = 0
        dfs(x - 1, y)
        dfs(x + 1, y)
        dfs(x, y - 1)
        dfs(x, y + 1)
        cnt+= 1 # 단지별 집 수 저장
        return cnt
    return cnt


for i in range(n):
    for j in range(n):
        c = dfs(i,j)
        if c>0:
            result.append(c)
            cnt =0

print(len(result))
result.sort()
print(*result, sep="\n")

배운점

전역 변수 사용: 변수 앞에 global 붙이기