[인프런 | DFS] 사다리타기(이차원 리스트 밑에서부터 이동)

사다리 타기(DFS)

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

특정목적지인 2에 도착하려면 7번 열 출발지에서 출발하면 됩니다.

 

▣ 입력설명
10*10의 사다리 지도가 주어집니다.

 

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

 

▣ 입력예제 1
1 0 1 0 0 1 0 1 0 1
1 0 1 1 1 1 0 1 0 1
1 0 1 0 0 1 0 1 0 1
1 0 1 0 0 1 0 1 1 1
1 0 1 0 0 1 0 1 0 1
1 0 1 1 1 1 0 1 0 1
1 0 1 0 0 1 0 1 1 1
1 1 1 0 0 1 0 1 0 1
1 0 1 0 0 1 1 1 0 1
1 0 1 0 0 2 0 1 0 1

 

▣ 출력예제 1
7

 

문제풀이

모든 출발지인 맨 위에서부터 출발하면 비효율적

 -> 목적지를 알고있기 때문에 목적지에서 출발해서 위로 올라가는 형식!

행이 0인 경우 종료하면 정답

 

문제해결
사다리 게임의 특성상 무조건 좌 -> 우 -> 하(거꾸로 가면 상) 순서를 지키면서 방향을 이동

import sys
sys.stdin = open("인프런.txt", "r")

def DFS(current_x, current_y) :
    visite_list[current_x][current_y] = True
    
    #지도의 맨 위쪽에 도달 하는 경우 종료
    if current_x == 0 :
        print(current_y)
    else :
        #<-- 왼쪽 이동(y-1)
        #왼쪽 끝인 0보다 크면서 갈수있는 길(1)인경우 아직 방문하지 않은 경우(False)
        if current_y-1 >= 0 and map_data[current_x][current_y-1] == 1 and visite_list[current_x][current_y-1] == False :
            DFS(current_x, current_y-1)
        #--> 오른쪽 이동(y+1)
        #오른쪽 끝인 n보다 크면서 수있는 길(1)인경우 아직 방문하지 않은 경우(False)
        elif current_y < 10-1 and map_data[current_x][current_y+1] == 1 and visite_list[current_x][current_y+1] == False :
            DFS(current_x, current_y+1)
        #위쪽 이동
        #왼쪽, 오른쪽 둘다 못가는 경우 위쪽으로 이동
        else :
            DFS(current_x-1, current_y)

map_data = []
for i in range(10) :
    data = list(map(int, input().split()))
    map_data.append(data)

visite_list = [[False] * 10 for _ in range(10)]

for w in range(10) :
    #출발지는 맨 아래인 9행, w열에서 시작
    if map_data[9][w] == 2 :
        DFS(9, w)