미소를뿌리는감자의 코딩
[백준 2024/02/15] 2667번 단지번호붙이기 본문
728x90
https://www.acmicpc.net/problem/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)
728x90
'코딩 테스트 > 백준' 카테고리의 다른 글
[백준 2024/02/17] 1068번 트리 (0) | 2024.02.17 |
---|---|
[백준 2024/02/15] 2606번 바이러스 (0) | 2024.02.15 |
[백준 2024/02/14] 5957번 Cleaning the Dishes (1) | 2024.02.14 |
[백준 2024/02/14] 9863번 Calling All Programmers (0) | 2024.02.14 |
[백준 2024/02/13] 1922번 네트워크 연결 (2) | 2024.02.13 |