[ BOJ 2667 ] 단지 번호 붙이기(Python)

문제

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

연결된 집의 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 출력하는 문제이다.
문제를 잘 읽지않아서 이전 문제와 마찬가지로 삽질을 했다. ⛏

문제 풀이

• visited 함수를 따로 만들지 않고, 한번 방문한 집은 0으로 값을 바꾸어서 다시 방문하지 않도록 했다.

1. 만약 현재 좌표(i,j)가 집이면 cnt를 1로 만들고, 현재 좌표를 집이 아닌 곳(0)으로 만들어준다.
2. queue에 (i,j) 를 넣어준다.
3. (i,j) 의 상하좌우가 집이면, (nx,ny) 를 queue에 넣어주고 cnt에 1을 더해준다.
   마찬가지로 (nx,ny)를 집이 아닌 곳(0)으로 만들어준다.
4. 연결된 곳을 모두 확인해서 queue가 비어있으면, answer 리스트에 cnt를 추가해준다.
   이 때 cnt는 각 단지에 속하는 집의 수이다.
5. answer 리스트의 길이는 단지의 수, answer의 요소는 각 단지에 속하는 집의 수가 된다.

코드

N = int(input())
li = [list(input().rstrip()) for _ in range(N)]

ans = []
dx = [1,-1,0,0]
dy = [0,0,-1,1]

for i in range(N):
    for j in range(N):
        if li[i][j] == "1":
            cnt = 1
            li[i][j] = "0"
            q = [(i,j)]
            while q:
                x,y = q.pop(0)
                for k in range(4):
                    nx = x + dx[k]
                    ny = y + dy[k]
                    if 0 <= nx < N and 0 <= ny < N:
                        if li[nx][ny] == "1":
                            q.append((nx,ny))
                            li[nx][ny] = "0"
                            cnt += 1
            ans.append(cnt)
ans.sort()       
print(len(ans))
for i in ans:
    print(i)