사다리 타기(DFS) - python

<문제>

 

현수와 친구들은 과자를 사먹기 위해 사다리 타기를 합니다. 사다리 표현은 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

 

<풀이>

나같은 경우는 이문제를 보고 어떻게 생각을 했냐면 출발지가 되는 경우의 수는 10가지가 있지만 도착하는 지점은 1가지로 동일하다고 생각을 했다. 그래서 사다리를 거꾸로 타서 답을 바로 도출해 내자 라는 생각을 했다( 문제를 풀기전에 어떻게 풀어야 빨리 풀지에 대한 생각하는 것을 연습하니까 이런 생각을 할 수 있게 된듯 강의에서도 실제로 이런 방식으로 푼다)

또한 사다리는 옆으로 갈 수있을때는 무조건 옆으로 가기에 나도 좌 우 를 먼저 확인하고 좌 우가 안됐을때 위로 갈 수 있는 경우가 있을경우 DFS안에 넣는 식으로 했다. 좌우가 들어갈경우 DFS호출 후에 break를 해서 재귀함수가 끝나고 나올 경우 더 확인안하게끔 했다.

또한 앞서 언급드렸던 이문제 같은경우 도착지부터 출발하면 답은 하나로 도출하기에 크게 신경쓸 부분은 없었다. 그냥 DFS에 들어간 값은 01에서 0으로 바꿔서 다시 돌아가지 않게끔 진행했다.

 

<코드>

import sys
def DFS(x,y): # x는 세로 담당, y는 가로 담당
    #print(x,y)
    if x == 0:
        print(y)
        sys.exit(0)
    else:
        for i in range(3):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<= nx < 10 and 0 <= ny < 10 and L[nx][ny] == 1:
                L[nx][ny] = 0
                DFS(nx,ny)
                #L[nx][ny] = 1
                break # 좌 우 가 우선순위이기에 들어갈경우 상 은 따로 확인안해도됨
L = [list(map(int,input().split())) for _ in range(10)]
dx = [0,0,-1] 
dy = [-1,1,0] # 순서를 좌 우 상 으로 해서 좌우 먼저 확인하게 함
a = 0
for i in range(10):
    if L[9][i] == 2:
        a = i
        break
DFS(9,a)

14번째줄에 주석처리한 부분(L[nx][ny] = 1) 이 부분이 어차피 답은 하나이기에 따로 안해도 정답이 나온다. 또한 for문에 break를 넣은 이유는 좌우를 확인해서 1이 있으면 거기를 가고 위로는 가면 안되기에 break를 했다.순서가 좌 우 상으로 dx,dy를 설정했기에 위로 먼저갈일은 없다.

역시 문제를 어떻게 풀어야하는지 충분히 생각을 해야겠다고 느꼈다.