[백준][2667] 단지 번호 붙이기

• 문제
  • 2667번: 단지번호붙이기
• 해설

import sys

sys.setrecursionlimit(99999)

size = int(sys.stdin.readline().strip())
mapping = [[0] * size for x in range(size)]

for i, x in enumerate(sys.stdin.readlines()):
    for j, y in enumerate(x.strip()):
        mapping[i][j] = int(y)

went_or_not = [[False for _ in range(size)] for _ in range(size)]

def is_in_map(x, y):
    return 0 <= x < size and 0 <= y < size

def dfs(x, y, res):
    went_or_not[x][y] = True
    candidates = [(x - 1, y), (x, y + 1), (x + 1, y), (x, y - 1)]
    for nx, ny in candidates:
        if is_in_map(nx, ny):
            if mapping[nx][ny] and not went_or_not[nx][ny]:
                res.append(1)
                dfs(nx, ny, res)
    return res

final_res = []
for x in range(size):
    for y in range(size):
        if mapping[x][y] != 0 and went_or_not[x][y] == False:
            res_ = dfs(x, y, [1])
            if len(res_) >= 1:
                final_res.append(len(res_))
final_res = sorted(final_res)
print(len(final_res))
for x in final_res:
    print(x)

• 포인트
  • dfs로 풀 생각
  • 각 단지안에 집 개수도 세야하니까 안가본(went_or_not이 False) 그리고 집(mapping에서 1)에서 시작하면서 list를 인자로 받아 늘리기