사다리타기질문

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.

import sys
def DFS(L,x,y):
    global cnt
    if a[x][y]==2:
        print(cnt)
        sys.exit(0)
    else:
        if L==0:
            for i in range(10):
                cnt=i
                ch[x][y]=1
                DFS(L+1,x,y+i)
                ch[x][y]=0
        else:
            path_count=0
            next_path=-1
            
            for j in range(3):
                xx=x+dx[j]
                yy=y+dy[j]
                if 0<=xx<10 and 0<=yy<10 and a[xx][yy]==1 and ch[xx][yy]==0 :
                    next_path=j
                    path_count+=1
                    
            
            #갈 수 있는 방향이 아래로 하나만 있는 경우
            if path_count==1:
                ch[xx][yy]=1
                DFS(L+1,x+dx[next_path],y+dy[next_path])
                ch[xx][yy]=0
            #여러 방향으로 이동이 가능
            elif path_count>1:
                for k in range(3):
                    xx=x+dx[k]
                    yy=y+dy[k]
                    if 0<=xx<10 and 0<=yy<10 and a[xx][yy]==1 and ch[xx][yy]==0  :
                        ch[xx][yy]=1
                        DFS(L+1,xx,yy)
                        ch[xx][yy]=0
                        
if __name__=="__main__":
    a=[list(map(int,input().split())) for _ in range(10)]
    dy=[1,-1,0]#우 좌 히
    dx=[0,0,1]
    cnt=0
    ch=[[0]*10 for _ in range(10)]
    DFS(0,0,0)

저는 up-bottom형식으로 탐색을 했는데 출력값이 아예나오지 않습니다. 어느 부분이 잘못되었는지 알 수 있을까요? ㅠㅠ

안녕하세요, 인프런 AI 인턴입니다.

tkv00님, 사다리타기 문제에서 출력값이 나오지 않는 문제를 겪고 계신 것 같네요. 주신 코드를 살펴보았을 때, 몇 가지 문제가 있을 수 있으니 차례대로 해결해 봅시다.

sys.exit(0)을 사용하면 프로그램이 바로 종료되어 버립니다. 따라서 sys.exit(0)을 호출하기 전에 cnt 값이 정상적으로 설정되었는지 확인해야 합니다.
for i in range(10) 루프 내에서 cnt=i를 설정하고 있지만, 사다리타기의 경우 특정 열에서만 시작하는 것이 아니라 주어진 시작점에서 탐색을 시작해야 합니다. cnt를 열 인덱스로 설정하는 것이 적절한지 다시 생각해 보셔야 할 것 같습니다.
초기 DFS 호출 시, 시작점에 대한 정확한 좌표가 주어져야 합니다. 사다리타기의 시작점이 (0,0)인지 확인하셔야 하며, 문제에서 다른 좌표가 주어진다면 그에 맞게 수정해야 합니다.
path_count와 next_path를 사용하여 이동 가능한 경로를 파악하는 로직이 있는데, 이 부분에서 x+dx[next_path], y+dy[next_path]를 사용하기 전에 next_path 값이 유효한지 확인하는 부분이 누락되어 있습니다. next_path가 유효한지 여부를 체크하고 사용해야 합니다.

이와 같은 점들을 고려하여 코드를 다시 검토하시고 디버깅을 해 보시기 바랍니다.
사다리타기 문제의 경우 이전 경로를 확인하여 사이클이 생기지 않도록 주의하면서 탐색해야 하므로, ch 배열을 사용하여 이미 방문한 경로를 체크하는 것이 중요합니다.
그리고 사다리타기 문제에 대한 자세한 알고리즘이나 예시가 필요하면 인프런의 알고리즘 강의를 참고하시면 도움이 될 수 있습니다.

추가적으로 이해가 잘 되지 않는 부분이나, 더 궁금한 점이 있으시면 질문 주시기 바랍니다.

감사합니다.

인프런 커뮤니티 질문&답변