Repository navigation
음료수 얼려먹기 실전문제 질문 #193
Description
안녕하세요. 음료수 얼려먹기 실전문제 이해가 안 가는 부분이 있어 질문드려요.
dfs 함수의 흐름이 헷갈려서 아래와 같이 print 구문을 각각의 재귀함수 밑에 적었는데요.
def dfs(x, y):
print(f'dfs x: {x}, y: {y}')
if x <= -1 or x >= n or y <= -1 or y >= m:
return False
if graph[x][y] == 0:
graph[x][y] = 1
print(f'\nnot visited x: {x}, y: {y}')
dfs(x - 1, y)
print("1st line")
dfs(x, y - 1)
print("2nd line")
dfs(x + 1, y)
print("3rd line")
dfs(x, y + 1)
print("4th line")
return True
return False
149p 에 있는 리스트 (바로 아래에 적었습니다) 를 예시로 테스트 해봤을 때,
00110
00011
11111
00000
not visited x: 0, y: 1
dfs x: -1, y: 1
1st line
dfs x: 0, y: 0
2nd line
dfs x: 1, y: 1
3rd line
dfs x: 0, y: 2
4th line
1st line # 질문1) 이 라인부터 6줄 아래까지 이해가 가지 않습니다
dfs x: 1, y: 0
2nd line
dfs x: 2, y: 1
3rd line
dfs x: 1, y: 2 #
not visited x: 1, y: 2 # 질문2) 이 부분이 이해가 가지 않습니다
dfs x: 0, y: 2
1st line
dfs x: 1, y: 1
2nd line
dfs x: 2, y: 2
3rd line
dfs x: 1, y: 3
4th line
4th line
4th line
3rd line
dfs x: 0, y: 1
4th line
이런 결과가 나오는데요.
결과 중 #1)로 표시한 부분의 결과가 이해가 되지 않습니다.
그래프 상 (0,1) 위치의 상하좌우의 값을 모두 탐색한 이후에 코드의 흐름이 어떻게 되는지,
왜 True를 return하지 않는지,
가장 마지막 부분의 #2) 로 표시한 부분은 그래프 상 (1,2)로, 값이 1인데 왜 print 값에는 'if graph[x][y] == 0:' 에 True가 된 건지 잘 모르겠습니다
DFS코드와 재귀함수의 흐름이 어려운데 어떻게 이해하면 될까요? 미리 감사드립니다.
Activity