[백준/Python] 단지번호붙이기

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

2667번: 단지번호붙이기

n = int(input()) # 지도 크기
graph = [list(map(int, input())) for _ in range(n)] # 지도
answer = [] # 단지 내 집의 수 리스트
count = result = 0 # 각 단지내 집의 수, 총 단지 수
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]

def dfs(x, y):
    if x <= -1 or x >= n or y <= -1 or y >= n: # 이동할 범위를 벗어난 경우
        return False

    if graph[x][y] == 1: # 집이 있다면
        global count
        count += 1 # 집의 수 +1
        graph[x][y] = 0 # 방문 처리를 해준다
        for i in range(4): # 좌, 우, 아래, 위 집을 방문한다
            dfs(x + dx[i], y + dy[i])
        return True
    return False

for i in range(n):
    for j in range(n):
        if dfs(i, j) == True: # 해당 단지내 모든 집의 방문이 끝났다면
            answer.append(count) # answer에 집의 수 저장
            result += 1 # 총 단지 수 +1
            count = 0 # 초기화

answer.sort() # 오름차순 정렬
print(result)
print(*answer)

1. 지도 크기, 지도를 입력받고 필요한 변수를 생성한다.

2. 지도의 집을 하나씩 돌면서 dfs를 수행한다.

    2-1. 해당 집을 방문할 수 있는 범위가 아니거나 이미 방문한 경우 → return False

    2-2. 해당 집을 방문할 수 있다면 방문 처리를 해주고 좌, 우, 아래, 위 집을 방문한다. 모든 방문이 끝나면 → return True

    2-3. 해당 단지 내 모든 집의 방문이 끝났다면 answer에 집의 수를 저장하고 result에 +1, count 초기화

3. 마지막으로 answer을 오름차순 정렬 후 결과 출력