- 문제 소개
- 조건
- 없음
- 코드
N = int(input())
board = []
for i in range(N):
board.append(list(input()))
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
cnt = 0
house = 0
house_stack = []
def dfs(x, y):
global house
house += 1
for k in range(4):
nx = x + dx[k]
ny = y + dy[k]
if nx >= 0 and ny >= 0 and nx < N and ny < N and board[nx][ny] == '1':
board[nx][ny] = '0'
dfs(nx, ny)
for i in range(N):
for j in range(N):
if board[i][j] == '1':
cnt += 1
board[i][j] = '0'
dfs(i, j)
house_stack.append(house)
house = 0
print(cnt)
house_stack.sort()
for i in house_stack:
print(i)- 해설
처음 입력되는 수 N은 정사각형 모양 단지의 한 변의 길이입니다. 그 다음 N번만큼 반복하면서 Board 배열을 채워줍니다. 상,하,좌,우 숫자를 탐색하기 위한 dx, dy를 지정해주고, 단지의 개수 cnt, 집의 개수를 새는 house, 이를 저장하기 위한 배열인 house_stack도 만들어주었습니다. 이중 for문을 통해서 탐색을 해주면서 현재 위치가 1이면 cnt를 1 추가해주고 현재 위치를 0으로 만들어서 방문했다는 표시를 합니다. 그리고 dfs를 돌아줍니다. dfs 내에선 상하좌우를 보면서 그 위치가 1이면 0으로 만들고 또 다시 dfs를 돌려줍니다. dfs를 한번 돌 때마다 집의 개수가 1씩 증가하고, dfs를 다 돌면 이 숫자를 house_stack에 추가해주고 house를 0으로 초기화해줍니다. 이를 반복하면서 단지의 개수와 집의 개수를 모두 찾을 수 있습니다.
