[Python Algorithm] 깊이/넓이 우선탐색(DFS, BFS) - 사다리 타기(DFS)

> 깊이/넓이 우선탐색(DFS, BFS) 활용 (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

 

import sys
input = sys.stdin.readline

board = [list(map(int, input().split())) for _ in range(10)]
ch = [[0]*10 for _ in range(10)]

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)
  


for y in range(10):
  if board[9][y] == 2:
    DFS(9, y)

 

⭐️ Point ! ⭐️

• 도착지점부터 출발점을 찾아가기 !!

 

 

 

 

출처

인프런 : 파이썬 알고리즘 문제 풀이