[인프런] 사다리 타기

---

문제설명

현수와 친구들은 과자를 사먹기 위해 사다리 타기를 한다. 사다리 표현은 2차원 배열로 되어 있으며, 0은 평면을 의미하고, 사다리는 1로 표현한다. 현수는 특정 도착지점으로 도착하기 위해서는 몇 번째 열에서 출발해야 하는지 알고 싶다. 특정 도착지점은 2로 표시된다. 주어지는 지도의 크기는 10 by 10이다.

 

입력조건

• 10 by 10의 사다리 지도가 주어진다.

출력조건

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

사고과정

• 스스로 풀 때 위에서 출발해야 한다는 것 떄문에 0행의 모든 열에서 DFS 탐색을 수행하면서 마지막 행에서 도착지점이면 출력하도록 했다. 그런데 이렇게 구현하려 하니 방문 체크용 테이블을 구현하는 데 살짝 애를 먹었따.. 결국 구현은 했다.
• 풀이를 보니, 역발상으로 도착지점에서 역으로 올라갔다. 따라서 도착지점을 이미 알고 있으므로 도착지점에서 DFS 탐색 1번만 수행하면 출발 지점을 알 수 있다...이러한 아이디어 하나가 시간 복잡도를 확 줄여주는 듯 하다. 문제 범위가 10으로 고정되어 있으니 다행이지 범위가 커지면 내 구현 풀이는 시간 초과에러가 발생할 게 분명하다..
• 또 사다리 게임의 특성상 무조건 좌 -> 우 -> 하(거꾸로 가면 상) 순서를 지키면서 방향을 이동해야 하는데, 나는 for loop를 돌면서 갈 수 있는 좌표가 발견된 순간 break하는 방식으로 풀이했지만 강사님은 애초에 좌, 우, 상 방향을 if ~ elif ~ else 구문을 사용하셨다. 배울점이 많다!

풀이

- 강의 풀이(권장!)

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 >= 0 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)

- 나의 풀이

board = [list(map(int, input().split())) for _ in range(10)]
visited = [[0] * 10 for _ in range(10)]
dx = [0, 0, 1]  # 좌, 우, 하 -> 순서 이대로 지켜야 함
dy = [-1, 1, 0]
answer = -1

def dfs(x, y):
    global answer
    visited[x][y] = 1
    # 도착점 도달했을 때, 방문 테이블의 0번째 행에서 1값을 갖고 있는 열이 출발지 열번호!
    if x == 9 and board[x][y] == 2:
        for j in range(10):
            if visited[0][j] == 1:
                answer = j
    else:
        for i in range(3):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < 10 and 0 <= ny < 10:
                if visited[nx][ny] == 0 and (board[nx][ny] == 1 or board[nx][ny] == 2):
                    dfs(nx, ny)
                    visited[nx][ny] = 0
                    break
    visited[x][y] = 0   # 나중에 출발점 찾기 위해서 시작좌표도 0으로 방문 체크 풀어주기


for j in range(10):
    if board[0][j] == 1:
        dfs(0, j)
print('answer:', answer)