[2667] 단지번호붙이기 In python

 

> dfs

> bfs

 

 

실행시간 약 112ms

 

 

해당 좌표의 위치가 집인지

그리고

해당 좌표에 방문했었는지 안했는지에 대한

조건이 중요했던 문제

 

 

from collections import deque

n = int(input())
array = [[] for _ in range(n)]
for i in range(n):
    for j in list(input()):
        array[i].append(int(j))
# 상,우,하,좌
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
answer = [[0 for _ in range(n)] for _ in range(n)]
cnt = 1

def bfs(i, j):
    queue = deque()
    queue.append((i, j))
    global cnt
    if array[i][j]: # array[i][j]가 집이면?
        answer[i][j] = cnt # 방문처리 겸 단지번호 기입
    while queue:
        x, y = queue.popleft()
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            if 0 <= nx < n and 0 <= ny < n:
                if array[nx][ny] and not answer[nx][ny]: 
                # array[nx][ny]가 집이고 answer[nx][ny]의 값이 0인 경우(= 아직 방문하지 않은 곳)
                    queue.append((nx, ny)) 
                    answer[nx][ny] = cnt


for i in range(n):
    for j in range(n):
        if not answer[i][j] and array[i][j]:
            bfs(i, j)
            cnt += 1 # 단지 값 +=1

real=[]
print(cnt-1) # 총단지수 출력
for i in range(cnt-1):
    result = 0
    for x in range(n):
        for y in range(n):
            if answer[x][y] == i+1:
                result += 1
    real.append(result)
real=sorted(real) # 오름차순 정렬
for i in real:
    print(i)