인프런 커뮤니티 질문&답변
작성한 질문수
사다리타기 (DFS)문제
작성
·
161
0
선생님 안녕하세요. 한가지 질문이 있습니다. 커뮤니티에 다른분이 올려주신 코드를 토대로 만들어 보았는데 답이 2가 나오더라고요....
def dfs안에
기존과 다르게 else:를 넣고 바로 dfs(r-1, c)를 해보니 답이 2가 나오는데 어떻게 해서 2가 나오는지 헷갈립니다.. ㅠㅠ
arr = [list(map(int,input().split())) for _ in range(10)]
for i in range(10):
if arr[9][i] == 2:
start = i
break
def dfs(r,c):
if r == 0:
print(c)
return
if 0<= c-1 and arr[r][c-1] == 1:
arr[r][c-1] = 2
dfs(r,c-1)
elif c+1 < 10 and arr[r][c+1] == 1:
arr[r][c+1] = 2
dfs(r,c+1)
else:
dfs(r-1,c)
dfs(9,start)답변 1
0
안녕하세요, 인프런 AI 인턴입니다.
else 구문을 추가하게 되면 사다리의 양 옆으로 이동할 수 없는 경우에 else 안의 dfs(r-1,c) 호출로 바로 위의 행으로 이동하게 됩니다. 그렇게 되면 사다리타기 경로가 제대로 고려되지 않으며 오류가 발생할 수 있습니다.
님께서 제시한 코드에서 else 아래의 dfs(r-1,c)는 양 옆에 갈 수 있는 길이 있다면 그 길을 우선적으로 선택해야 하는 사다리타기 규칙을 무시하고, 언제나 가능한 위쪽 칸으로 바로 이동하게 만듭니다. 이는 문제의 규칙에 어긋나서 잘못된 결과를 얻을 수 있습니다.
실제 문제에서 사다리를 타는 규칙을 잘 생각하여 코드를 수정해보시기 바랍니다. 옆에 길이 있으면 먼저 옆으로 이동해야 하고, 양 옆에 이동할 길이 없을 때만 위로 올라가는 로직이 필요합니다. else 구문을 사용하는 대신, 양 옆을 확인 후 이동할 수 없을 때만 dfs(r-1,c)를 호출하는 것을 생각해보세요.
글로만 설명드리는 것보단 실제 해당 함수를 분석해가며, 어떤 경로로 함수가 호출되고, 어떻게 다음 이동을 결정하는지 종이에 그려보거나 디버깅하며 확인하시면 더 이해하기 쉬울 것입니다.
추가적인 질문이 있으시면 해당 강의의 커뮤니티 질문&답변 게시판에 올려주시면 강사님이 직접 확인하시고 조언해 주실 겁니다.
학습에 도움이 되시길 바랍니다. 감사합니다.