재귀응용 2 --- Counting cells in a Blob(with Python)

 

인접 하고 색칠된 박스의 모음을 

1칸 이내로 있다면 한 단락으로 인식하여

각 구간으로 나누는 문제를 풀어보고자 한다. 

---

 

입력은  n*n 크기의 2차원 그리드

하나의 좌표(x,y) 

 

출력은 : (x,y)가 포함된 blob의 크기다.

(x,y)가 어떤 blob에도 속하지 않는 경우에는 0을 출력한다. 

 

---

 

 

즉, (x,y) 좌표를 따라 자신이 색칠 되어있다면(아니라면 0) ,  bfs를 실행시켜 자신 주변에 한칸 이내로 떨어진 색칠된 박스들의 개수를 구해주면 된다. 

 

재귀함수로 구현해보자 (보통의 경우 while을 사용하여 q를 다루겠지만 여기서는 재귀를 사용할 것이다)

n = int(input())
graph = []
num = []

for i in range(n):
    graph.append(list(map(int, input())))
Ax,Ay = map(int,input().split())

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


def DFS(x, y):
    if x < 0 or x >= n or y < 0 or y >= n:
        return False

    if graph[x][y] == 1:
        global count
        count += 1
        graph[x][y] = 0
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            DFS(nx, ny)
        return True
    return False


count = 0
if DFS(Ax,Ay) == True:
    print(count)
else:
    print(-1)

 

왜 자꾸 재귀만 배운 우리들에게 이러한 문제를 가져오는가? 

 

모든 실행이 계속해서 같은 방식으로 찾기때문에 자기자신을 찾는 재귀를 사용하여 해당 문제를 푸는 것이다. 

아직 dfs, bfs를 알려주지 않았지만 해당 메서드는 자신을 호출함으로써 계속해서 연결된 박스를 찾아가기때문에 어렵지 않게 이해할 수 있을 것이다.