[알고리즘] 사다리 타기(DFS)

(문제) 사다리 타기(DFS)

---

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

사다리 표현은 2차원 평면은 0으로 채워지고, 사다리는 1로 표현합니다.

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

특정 도착지점은 2로 표기됩니다.

여러분이 도와주세요.

사다리의 지도가 10 * 10이면

특정목적지인 2에 도착하려면 7번 열 출발지에서 출발하면 됩니다.

입력설명

10 * 10의 사다리 지도가 주어집니다.

출력설명

출발지 열 번호를 출력하세요.

테스트케이스

입력예제	출력예제
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	7
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 1 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 2 0 0 1 0 1 0 1	5
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 1 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 1 1 0 1 1 0 1 0 0 1 1 1 0 1 1 0 1 0 0 2 0 1 0 1	0
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 1 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 1 1 0 1 1 0 1 0 0 1 1 1 0 1 1 0 1 0 0 1 0 1 0 2	9
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 1 1 0 1 1 0 1 0 0 1 0 1 1 1 1 1 1 0 0 1 1 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 1 1 0 1 1 0 1 0 0 1 1 1 0 1 1 0 1 0 0 1 0 1 0 2	7

---

해결방법

1. 가장 위에 즉, 0행에서 값이 1인 경우에서 시작하기 때문에 반복문을 0~9까지 1의 값에 있는 0행 기준으로 돈다.
2. 반복할 때, 들린 곳을 저장하는 리스트는 0으로 전부 초기화 한다.
3. 우선 왼쪽, 오른쪽, 아래 순으로 순회를 할 것이다. 그리고 만약 아래로 내려가야하는 곳이 없을 경우 즉 return을 했을 경우, 반복문을 break하여 순회를 빠져 나온다.
4. 들렸던 곳을 저장하는 리스트에 들리지 않은 곳을 순회한다. 순회할 경우 들렸던 곳은 들렸다고 체크를 한다.
5. 그래서 조건은 지금가려고 하는 곳의 좌표가 들렸던 곳이 아니거나 가려고 하는 곳에 1의 값이 있으면 그 곳으로 움직인다.
6. 이 반복은 행이 9가 될 때 까지 반복이 되며, 만약 2를 만났을 경우 1번에서 0행에 시작한 x열을 print한다

동작 시각화

반복문을 돌려서 가장 위에 있는 행을 순회하여 1이 있는 곳부터 시작을 한다.

들렸던 곳을 저장하는 리스트

• 0인덱스

---

• 2인덱스

---

• 5인덱스

---

• 7인덱스

---

• 9인덱스

---

코드

import sys

def DFS(L, x, y):
    if x == 9 and maps[x][y] == 2:
        print(L)
        sys.exit(0)
    elif x == 9 and maps[x][y] == 1:
        return
    else:
        # 왼쪽 오른쪽 밑에 체크하기
        for i in range(3):
            if 0 <= x + dx[i] < 10 and 0 <= y + dy[i] < 10:
                # 0이 아닌 다른 것들
                if maps[x + dx[i]][y + dy[i]] != 0:
                    #  내가 가보지 못한 곳으로 가기
                    if ch_maps[x + dx[i]][y + dy[i]] != 1:
                        ch_maps[x][y] = 1
                        DFS(L, x + dx[i], y + dy[i])
                        # 만약 마지막 까지 돌았을 때, 밑으로 가는게 없을 경우 반복문 끝낸다!
                        break


maps = [list(map(int, input().split())) for _ in range(10)]

# 좌, 우, 하
# 행
dx = [0, 0, 1]
# 열
dy = [-1, 1, 0]

for j in range(10):
    ch_maps = [[0] * 10 for _ in range(10)]
    if maps[0][j] == 1:
        DFS(j, 0, j)