[파이썬 알고리즘 문제풀이] - Section7 / 깊이/넓이 우선 탐색(DFS, BFS) 활용 - 16

😀 사다리 타기

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

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

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

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

import sys
sys.stdin = open("input.text", "rt")
sys.setrecursionlimit(10**6)
from collections import deque

g = [list(map(int, input().split())) for _ in range(10)]

#도착지 좌표
max_data = -242424
a = 9 #행
b = g[9].index(2) #열 2를 가지고 있는 열 가져와야지 
# print(a,b)
def DFS(x,y):
    if x == 0: #시작점 도착. 종료조건
        print(y)
        exit()
    else:
        #왼,오 1이면 무조건 가야함
        if 0<=y-1<10 and g[x][y-1] == 1:
            g[x][y-1] = 0
            DFS(x,y-1)
            g[x][y-1] = 1
        elif 0<=y+1<10 and g[x][y+1] == 1:
            g[x][y+1] = 0
            DFS(x,y+1)
            g[x][y+1] = 1
        else:
            g[x-1][y] = 0
            DFS(x-1,y)
            g[x-1][y] = 1
DFS(a,b)
        

⚽ 코멘트

이 문제는 읽으면서 유형을 파악했어야 했다. 0,1 표시. 즉 그래프 문제였고, 출발지부터 시작해서 도착지점까지... 이 표현을 보고 DFS, 즉 깊이우선탐색. 끝까지 들어가는 것을 느낄 수 있었어야 했다.

근데 여기서 헷갈렸던 것이 그렇다고 하더라도 어떻게 2까지 찾아갈지.. 모든 경우를 다 따진다면 굉장히 오래걸릴 것이다.

그렇기에 발상의 전환으로 도착지에서 DFS를 시작해서 시작점으로 이동하는 것을 생각했다면 쉽게 풀 수 있었을 것이다. 결국 도착지에서 출발시키면 몇번째 열에서 도달하는지 알 수 있으므로 그것이 정답이 되는 것이다 !

• 이 출발지에서 시작하는 것이 아닌 도착지에서 시작하는 것도 잘 생각해주자.

• 모든 열을 확인하는 것은 비효율적이라는 것을 빨리 판단하고 역으로 사다리 타는 것을 생각했어야 했다.

• DFS는 종료조건 먼저 생각하고, 가지를 어떻게 뻗어나가야 할지 생각하면 그걸 코드로 구현하면 끝.