사다리 타기(DFS)
깊이/넓이 우선 탐색(DFS, BFS) 활용
문제 ✏️
사다리 타기(DFS)
현수와 친구들은 과자를 사먹기 위해 사다리 타기를 합니다. 사다리 표현은 2차원 평면은 0으로 채워지고, 사다리는 1로 표현합니다. 현수는 특정도착지점으로 도착하기 위해서는 몇 번째 열에서 출발해야 하는지 알고싶습니다. 특정 도착지점은 2로 표기됩니다. 여러분이 도와주세요. 사다리의 지도가 10*10이면
특정목적지인 2에 도착하려면 7번 열 출발지에서 출발하면 됩니다.
▣ 입력설명
10*10의 사다리 지도가 주어집니다.
▣ 출력설명
출발지 열 번호를 출력하세요.
코드 💻
import sys
#sys.stdin = open("input.txt", "rt") # read text
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)
참고
- 인프런 : 파이썬 알고리즘 문제 풀이
Author And Source
이 문제에 관하여(사다리 타기(DFS)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jsj3282/사다리-타기DFS저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)