백준) 단지번호붙이기

 

 

 

 

섬의 개수라는 문제와 로직이 거의 동일한 문제다.

'섬의 개수' 문제와 살짝 응용이 필요한 '단지 번호 붙이기' 문제 2개를 풀고 나면 DFS의 기본을 마스터했다고 말할 수 있을 것이다.

 

dx와 dy에 상하좌우 정보를 미리 담아 활용하는 방식이 인상적이고 한 번에 생각하기 힘든 방식인 것 같다.

그리고 리스트는 주소 값만 전달한다는 점을 이용해서 dfs의 어느 곳에서든지 land라는 리스트에 접근할 수 있게 코드를 짰다.

import sys

inputs_len = int(sys.stdin.readline()[:-1])
inputs = [list(sys.stdin.readline()[:-1]) for _ in range(inputs_len)]


dx = [0,0,1,-1]
dy = [1,-1,0,0]

m = len(inputs)
n = len(inputs[0])

def dfs(r,c,num):
    if r < 0 or c < 0 or r >= m or c >= n or inputs[r][c] == '0':
        return

    inputs[r][c] = '0'
    num.append([r,c])

    for i in range(4):
        dfs(r + dx[i], c + dy[i], num)
    return


land = []
for i in range(m):
    for j in range(n):
        if inputs[i][j] != '1':
            continue

        num = []
        dfs(i,j,num)
        land.append(len(num))

land.sort()
print(len(land))
for i in land:
    print(i)