[백준 2024/02/15] 2667번 단지번호붙이기

https://www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

 

1. 접근 방법

집 주위로 상하좌우를 search 한 다음, 집이 있다면, 해당 집에 대해서 다시 search를 하는 방식으로 코드를 진행하였다.

 

방문을 완료했다면, 중복 계산하는 것을 막기 위해, 해당 집을 0으로 바꾸어주었다.

def house(i, j):
    if not (0 <= i < length and 0 <= j < length) or grid[i][j] == '0':
        return 0
    grid[i][j] = '0'
    return 1 + house(i, j - 1) + house(i, j + 1) + house(i - 1, j) + house(i + 1, j)

 

이런식으로 작성해주었다. 

return 1 + house(i, j - 1) + house(i, j + 1) + house(i - 1, j) + house(i + 1, j)

이 부분에 대해서 이야기 해보도록 하겠다. return 1 + 를 하는 것은, 이미 grid[i][j]=='0' 인 if 문을 통과한 것이기 때문에, 1을 더해준 것이다. -> 즉, 해당 위치에 집이 있기 때문에 1을 더해준 것이다.

 

이후 상하좌우에 다시 house가 있는지 재귀적으로 찾았다.

 

return 1 + house를 작성하는 것이 진짜 그 함수에서 return 하는 것처럼 느껴졌었다. 하지만, 재귀적으로 선언된 함수에서 return 하는 것은, 루트 함수에 값을 전달해주는 과정 그 이상 그 이하도 아님을 깨달았다. 즉, 함수를 나가는 return 문이 아닌, 값을 돌려주는 return 문임을 생각하게 되었다.

2. 코드

grid = []
length = int(input())
for _ in range(length):
    line = input()
    grid.append([char for char in line])

def house(i, j):
    if not (0 <= i < length and 0 <= j < length) or grid[i][j] == '0':
        return 0
    grid[i][j] = '0'
    return 1 + house(i, j - 1) + house(i, j + 1) + house(i - 1, j) + house(i + 1, j)


result = []
for i in range(length):
    for j in range(length):
        if grid[i][j] == '1':
            size = house(i, j)
            result.append(size)

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