2667 단지번호붙이기 / DFS, BFS

 

정답

• 방문한 지점은 다시 방문할 수 없도록 해당 좌표의 값을 1로 변경해야 함
• 큐에서 해당 노드를 뺄 때는 while문 아래에서 빼야 함

from collections import deque
n = int(input()) # n * n 형태의 지도의 크기

# 지도 세팅
maze = []
for _ in range(n):
    row = input()
    char_row = list(row)
    int_row = list(map(int, char_row))
    maze.append(int_row)

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

def BFS(x, y):
    queue = deque()
    queue.append((x, y))
    maze[x][y] = 0
    count = 1

    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            # 범위가 안되면 skip
            if nx >= n or ny >= n or nx < 0 or ny < 0:
                continue

            # 0 이라면 skip
            if maze[nx][ny] == 0:
                continue

            # 탐색 할 수 있는 범위라면 count 증가
            if maze[nx][ny] == 1:
                queue.append((nx, ny))
                maze[nx][ny] = 0 # 방문한 지점은 다시 재방문 할 수 없도록 0으로 변경
                count = count + 1

    return count

aprt = []
ans = 0

# 지도 탐색 시작
for i in range(n):
    for j in range(n):
        if maze[i][j] == 1:
            aprt.append(BFS(i, j))
            ans = ans + 1

aprt.sort()
print(ans)
for i in aprt:
    print(i)