사다리 타기 (DFS)

생성일: 2022년 2월 19일 오후 4:39

구현 코드

# 사다리 타기 (DFS)
import sys
sys.stdin = open("input.txt", "rt")

def DFS(L, x, y):
    if x == 9:
        if board[x][y] == 2:
            print(L)
            sys.exit()
    else:
        if 0<=y-1<10 and board[x][y-1] == 1:
            board[x][y] = 0
            DFS(L, x, y-1)
            board[x][y] = 1
        elif 0<=y+1<10 and board[x][y+1] == 1:
            board[x][y] = 0
            DFS(L, x, y+1)
            board[x][y] = 1
        else:
            board[x][y] = 0
            DFS(L, x+1, y)
            board[x][y] = 1

if __name__ == "__main__":
    board = []
    for _ in range(10):
        board.append(list(map(int, input().split())))

    people = [0, 2, 5, 7, 9]
    for x in people:
        DFS(x, 0, x)

모범 답안

import sys
sys.stdin=open("input.txt", "r")
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)

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)

차이점

• 내가 구현한 코드는 각 사다리의 경로를 탐색해서 당첨인 사람을 찾는 로직이지만 모범 답안에서는 거꾸로 당첨칸에서부터 위로 올라오면서 어떤 사다리가 당첨이 될 사다리인지를 찾는 로직이다.
• 모범 답안처럼 하는 것이 당첨이 아닌 사다리 경로를 찾는 낭비를 거치지 않기 때문에 효율적이다.