[Python] 2667 단지번호붙이기

 

 

풀이

#BFS

각각의 집 별로 상하좌우를 검사해야 한다. 검사했다면 해당 집의 상하좌우를 검사해가고.. 또 해당 집 주변을 검사.. 없다면 이전 식으로 돌아가기 -> 이를 반복

즉 모든 집에 대해 각각 상하좌우를 검사하자 -> 전수 검사 중 BFS or DFS! -> BFS를 선택

검사한 집은 0으로 바꾸어 다시 방문하지 않도록 하기

BFS로 한 단지내의 모든 집을 검사, 한 단지(=고립된 한 그래프) 검사 끝나면 BFS 종료됨 => 단지 리스트에 해당 집 수를 추가하기

이후 지도(maps)에서 1이 남아있는 집을 검사하고, 존재할시에 BFS를 호출하여 검사 

from collections import deque

# 1. 입력을 이중리스트에 저장하기
n = int(input())
maps = [] # maps를 내장된 함수인 map이라 선언해서 오류가..

for _ in range (n):
    maps.append(list(map(int, input().strip())))
# 띄어쓰기 없는 줄로 이중리스트로 받아오기
# strip은 앞뒤 공백을 없애주는 함수!
    

# 2. 총 단지 수와 단지 내 집 수 구하기 
houses = []

def BFS(x, y):
    dx = [-1, +1, 0, 0] #상하좌우 표현 위한 방향 리스트
    dy = [0, 0, -1, +1] 
    house = 0
    q = deque() 
    q.append((x, y)) # 처음 것 방문, q에 x,y의 튜플 형태로 넣을 것임
    while q:
        x, y = q.popleft()
        if x < 0 or y < 0 or x >= n or y >= n or maps[x][y] == 0:
        # 범위가 벗어나면 out
            continue
        maps[x][y] = 0
        house += 1
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            q.append((nx, ny))
    return house
        
for i in range(n):
    for j in range(n):
        if maps[i][j] == 1:
            houses.append(BFS(i, j))

houses.sort()

print(len(houses))
for h in houses:
    print(h)