백준 2667 단지번호붙이기

단지번호붙이기

풀이 계획

• 전체 배열에 대해 BFS 진행하면서 개수 세기 (DFS, BFS 상관 없어보임)
• 단지 총 개수와, 각 단지 별 세대 수 세야 함.

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**8)

N = int(input())
map_lst = []
ans_lst = []
total_ans = 0
for _ in range(N):
    lst = list(map(int, input()))
    map_lst.append(lst)

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

def dfs(x, y):
    global ans
    # 리스트 유효 범위 내인지 확인
    if x < 0 or x >= N or y < 0 or y >= N:
        return False
    # 방문하지 않은 곳이면 재귀적으로 탐색
    if map_lst[y][x] != 0:
        map_lst[y][x] = 0
        ans += 1
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            dfs(nx, ny)
        return True
    return False

global ans
for i in range(N):
    for j in range(N):
        ans = 0
        res = dfs(i, j)
        if res == True:
            total_ans += 1
            ans_lst.append(ans)
ans_lst.sort()

# 출력
print(total_ans)
for i in ans_lst:
    print(i)

• 입력 받은 자료 자체를 변경하는 것은 위험하다고 들었음.
• 나중에 필요할 때는 따로 visited 배열을 만들어야 할 듯.