2667. 단지번호붙이기

문제

백준 2667번 단지번호붙이기

---

풀이

보자마자 dfs로 풀어야지라고 생각했다.. 제일 만만한가...?

입력이 공백구분없이 들어오기 때문에 문자열 한 줄씩 각 문자에 대해 타입변환하여 입력받았다.

board에서 1을 만날 때마다 단지 하나를 추가하고 dfs()를 호출하여 단지 내 집들을 탐색한다.

dfs()에서 board[x][y]의 값에 따라 처리하는데,

1. board[x][y]가 0인 경우 -> return
2. board[x][y]가 1인 경우
   해당 위치를 0으로 변경
   해당 단지의 집 수 + 1
   (x,y)의 상하좌우 탐색
   
   

def dfs(x, y):
    if board[x][y] == 0: return
    else:
        board[x][y] = 0
        cnt[-1] += 1
        for xx, yy in [[x+1, y], [x, y+1], [x-1, y], [x, y-1]]:
            if 0 <= xx < n and 0 <= yy < n and board[xx][yy]:
                dfs(xx, yy)

if __name__ == '__main__':
    n = int(input())
    board = [[int(i) for i in input()] for _ in range(n)]
    cnt = []
    for i in range(n):
        for j in range(n):
            if board[i][j]:
                cnt.append(0)
                dfs(i, j)
    cnt.sort()
    print(len(cnt))
    for x in cnt: print(x)

---

부족한 점

풀이 시간을 더 단축시키자