[파이썬(python)] 이것이 취업을 위한 코딩테스트다 음료수 얼려먹기

아직 dfs를 잘 모르는것 같아 dfs 예제를 풀어봤다.

 

n, m = map(int, input().split())
ice = []

for i in range(n):
    ice.append(list(map(int,input())))


count = 0

def dfs(i, j):

    if i < 0 or i >= n or j < 0 or j >= m:
        return False
    if ice[i][j] == 1:
        return False
    
    ice[i][j] = 1

    dfs(i+1, j)
    dfs(i, j+1)
    dfs(i-1, j)
    dfs(i, j-1)

    return True


for i in range(n):
    for j in range(m):
        if dfs(i, j) == True:
            count += 1

print(count)

 

 

그런데 내가 이해가 안갔던 포인트 하나.

범위를 벗어나거나, 얼음이 아닌경우 false를 리턴하게 되는데.. 

 

그러면 dfs를 다 끝내기도 전에 false가 먼저 리턴돼서 count가 증가할 수 없는 것 아닌가???

 

다시말하면 if dfs(i, j) == True 라는 문장을 실행할 떄 dfs의 가장 마지막에 True가 리턴되는데

그전에 재귀로 호출된 dfs가 먼저 False를 리턴하면....

뭐지? 어떻게 되는거지? 를 계속 고민했다..

 

 

그런데 다시생각해보니 재귀로 호출된 dfs는

dfs(i+1, j)
dfs(i, j+1)
dfs(i-1, j)
dfs(i, j-1)

이것인데.. False를 if dfs(i, j) == True로 리턴하지 않는다. 호출된 코드로 리턴되겟지.. 근데 그 호출된 코드는 리턴값을 저장하지 않으니까 그냥 넘겨지는것이다^^...

별것을 다 고민함