❗️[알고리즘]사다리타기

문제

현수와 친구들은 과자를 사먹기 위해 사다리 타기를 합니다. 사다리 표현은 2차원 평면은 0으 로 채워지고, 사다리는 1로 표현합니다. 현수는 특정도착지점으로 도착하기 위해서는 몇 번째 열에서 출발해야 하는지 알고싶습니다. 특정 도착지점은 2로 표기됩니다. 여러분이 도와주세 요. 사다리의 지도가 10*10이면

특정목적지인 2에 도착하려면 7번 열 출발지에서 출발하면 됩니다.
▣ 입력설명
10*10의 사다리 지도가 주어집니다.

▣ 출력설명
출발지 열 번호를 출력하세요.

입력예제 1

1010010101
1011110101
1010010101
1010010111
1010010101
1011110101
1010010111
1110010101
1010011101
1010020101

출력예제 1

7

[내 코드(틀린 코드)]

def DFS(L,x,y):
    global cnt
    if a[x][y]==2:
        print(cnt)
        sys.exit(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)]
    dx = [0, 0, -1]  # 아래, 오른쪽, 왼쪽으로 이동
    dy = [1, -1, 0]
    for i in range(10):  # 각 열에서 시작
        cnt = i  # 현재 시작 열 저장
        ch = [[0]*10 for _ in range(10)]  # 방문 표시 배열 초기화
        DFS(0, 0,i)  # 0행 i열에서 DFS 시작

1.DFS함수 내에서 각 열 탐색구현을 시도하였음.
2.0행부터 차례대로 탐색해서 특정좌표의 배열값이 2가 될 때를 중단조건으로 설정
3. 이동할 수 있는 길을 좌우,하로 구분하여 DFS탐색을 실행

실행시 출력값이 안나오는데 어느 부분이 잘못되었는지 아직 파악하지못함.

[해설코드]

def DFS(x,y):
	ch[x][y]=1
    if x==0:
    	print(y)
    else:
    	if y-1>=0 and board[x][y-1]==1 and ch[x][y-1]==0:
        	DFS(x,y-1) #왼쪽으로 이동
       elif y+1<10 and board[x][y+1]==1 and ch[x][y+1]==0:
       		DFS(x,y+1) #오른쪽으로 이동
       else:
       		DFS(x-1,y)#위로 이동
	
if __name__=="__main__":
	board=[list(map(int,input().split())) for _ in range(10)]
    ch=[[0] *10 for _ in range(10)]
    for y in range(10):
    	if board[9][y]==2:
        	DFS(9,y)

1. 시작을 0행부터 시작하면 비효율적->9행의 2인 열부터 시작해서 탐색
2. DFS탐색 시 레벨에 한정지어서 생각하지말자!