Algorithm - 사다리 타기(DFS)

 

알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다.
개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다.

 

문제

[사다리 타기(DFS)]

 

현수와 친구들은 과자를 사먹기 위해 사다리 타기를 한다.

사다리 표현은 2차원 리스트에 0과 1로 채워지며, 0은 평면을 의미하고 1은 사다리를 의미한다.

현수는 특정 도착지점으로 도착하기 위해 몇 번째 열에서 출발해야 하는지를 알고 싶어한다.

여기서 특정 도착지점은 2로 표기된다.

 

위의 조건을 모두 만족하는 프로그램을 작성하시오.

참고로, 사다리의 지도가 10 * 10이면 아래와 같이 2차원 리스트로 표현된다.

 

10 * 10 사다리 지도

 

위의 조건들을 고려하여, 특정 도착지점인 2에 도달하려면 7번째 열에서 출발하면 된다.

단, 사다리 타기의 특성 상 네 방향(상하좌우) 모두 이동이 가능할 경우에는 항상 좌우 방향의 이동이 상하 방향의 이동보다 우선된다. 

 

 

*입력 설명

10 * 10의 사다리 지도가 입력된다.

 

*출력 설명

출발지의 열 번호를 출력한다.

 

 

---

 

 

풀이(Python)

답안

import sys
sys.stdin = open('AA/input_71.txt', 'rt')

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)
            
# 출력 : 7

 

input_71.txt(입력)

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. DFS() 함수 내에 else절에서 if-elif-else 구문은 사다리 타기의 특성을 고려하여 상하좌우 방향의 DFS 탐색 매커니즘을 코드로 표현한 것이다.
2. 즉, DFS 탐색을 할 경우에 항상 좌우를 먼저 고려하여 이동할 수 있는지를 확인하고 그 이후에 상방으로 이동할 수 있는지를 고려하는 원리이다. (bottom-up 방식)
3. 참고로, 해당 문제를 푸는 접근방식은 bottom-up 방식의 DFS 탐색이다. (도착지점에서 출발하여 출발지점을 찾는 방식)
4. 즉, 2의 값을 가지는 사다리 지도 9행의 특정 열번호에서 DFS 탐색을 시작하여 위로 이동해가며 시작 지점을 찾는 방식이다.
5. 또한, 변수 x는 행번호를, 변수 y는 열번호를 의미한다.