Welcome to My IT World

문제

땅따먹기를 하다 질린 재하와 영훈이는 땅따먹기의 변종인 새로운 게임을 하기로 했습니다. 이 게임은 그림과 같이 n*n 크기의 격자에 각 1부터 9 사이의 정수를 쓴 상태로 시작합니다. 각 차례인 사람은 맨 왼쪽 윗 칸에서 시작해 외발로 뛰어서 오른쪽 아래 칸으로 내려가야 합니다. 이 때 각 칸에 적혀 있는 숫자만큼 오른쪽이나 아래 칸으로 움직일 수 있으며, 중간에 게임판 밖으로 벗어나면 안 됩니다.

균형을 잃어서 다른 발로 서거나 넘어져도 게임에서 집니다만, 재하와 영훈이는 젊고 활기차기 때문에 외발로 뛰어다니는 것은 아무것도 아닙니다. 다만 걱정되는 것은 주어진 게임판에 시작점에서 끝점으로 가는 방법이 존재하지 않을 수도 있다는 것입니다. 예를 들어 그림 (a)의 게임판에서는 사각형으로 표시된 칸들을 통해 끝에 도달할 수 있지만, 숫자가 하나 바뀐 그림 (b)에서는 그럴 수가 없습니다.

게임판이 주어질 때 왼쪽 위의 시작점에서 오른쪽 아래의 시작점에 도달할 수 있는 방법이 있는지 확인하는 프로그램을 작성하세요.

입력

입력의 첫 줄에는 테스트 케이스의 수 C(C <= 50)가 주어집니다. 각 테스트 케이스의 첫 줄에는 격자의 크기 n(2 <= n <= 100)이 주어지고, 그 후 n줄에 각 n개의 숫자로 왼쪽 위부터 각 칸에 쓰인 숫자들이 주어집니다. 오른쪽 아래 있는 끝 점 위치에는 0이 주어집니다.

출력

각 테스트 케이스마다 한 줄로, 시작점에서 끝 점으로 도달할 수 있을 경우 "YES"를, 아닐 경우 "NO"를 출력합니다. (따옴표 제외)

예제 입력

2 7 2 5 1 6 1 4 1 6 1 1 2 2 9 3 7 2 3 2 1 3 1 1 1 3 1 7 1 2 4 1 2 3 4 1 2 3 3 1 2 3 4 1 1 5 2 9 4 7 0 7 2 5 1 6 1 4 1 6 1 1 2 2 9 3 7 2 3 2 1 3 1 1 1 3 1 7 1 2 4 1 2 3 4 1 3 3 3 1 2 3 4 1 1 5 2 9 4 7 0

예제 출력

YES NO

출처 : https://algospot.com/judge/problem/read/JUMPGAME

[접근방식]

1. 완전탐색? ⇒ 재귀로 가능하나, 단순 완전탐색은 시간복잡도 때문에 불가능
2. 메모이제이션? ⇒ 2차원배열 cache 사용 but 실제로 사용해보니, dfs탐색할 때 visited처리랑 똑같은듯
3. 풀이방식 dfs로 탐색해주면서 cache(visited)라는 2차원 배열에 업데이트하고 만일 cache에 이미 있으면 넘기고 없을때만 cache에 업데이트하는 방식으로 진행 이 때, 도달할 수 없다면 같은 셀을 계속 돌게되고 그 때마다 cache 값이 존재할 것이므로 dfs가 추가적으로 불리지 않고 끝나게 될 것 마지막에 cache[n-1][n-1]이 여전히 초기값(0)이면, 도달할 수 없는 것이고 0보다 크면 도달가능

[풀이코드]

#입력값
n = 7
# board = [
#     [2, 5, 1, 6, 1, 4, 1],
#     [6, 1, 1, 2, 2, 9, 3],
#     [7, 2, 3, 2, 1, 3, 1],
#     [1, 1, 3, 1, 7, 1, 2],
#     [4, 1, 2, 3, 4, 1, 2],
#     [3, 3, 1, 2, 3, 4, 1],
#     [1, 5, 2, 9, 4, 7, 0]]

board = [
    [2, 5, 1, 6, 1, 4, 1],
    [6, 1, 1, 2, 2, 9, 3],
    [7, 2, 3, 2, 1, 3, 1],
    [1, 1, 3, 1, 7, 1, 2],
    [4, 1, 2, 3, 4, 1, 3],
    [3, 3, 1, 2, 3, 4, 1],
    [1, 5, 2, 9, 4, 7, 0]]

dir = [(1,0), (0, 1)]
cache = [[0]*n for _ in range(n)]

def dfs(r, c):
    global board, dir, cache, n
    if r == n-1 and c == n-1:
        return
    steps = board[r][c]
    for i in range(2):
        nxt_r = r + steps*dir[i][0]
        nxt_c = c + steps*dir[i][1]
        if nxt_r < 0 or nxt_r >= n or nxt_c < 0 or nxt_c >= n:
            continue
        if cache[nxt_r][nxt_c] > 0:
            continue
        else:
            cache[nxt_r][nxt_c] = steps + cache[r][c]
            dfs(nxt_r, nxt_c)

dfs(0, 0)
if cache[n-1][n-1] > 0:
    print('Yes')
else:
    print('No')

여기서는 도착여부만 판단하므로 cache(visited)의 초기값을 False로 두고 True/False로 표기해도 될 것으로 판단됨

[책 풀이]

#입력값
n = 7
board = [
    [2, 5, 1, 6, 1, 4, 1],
    [6, 1, 1, 2, 2, 9, 3],
    [7, 2, 3, 2, 1, 3, 1],
    [1, 1, 3, 1, 7, 1, 2],
    [4, 1, 2, 3, 4, 1, 2],
    [3, 3, 1, 2, 3, 4, 1],
    [1, 5, 2, 9, 4, 7, 0]]

# board = [
#     [2, 5, 1, 6, 1, 4, 1],
#     [6, 1, 1, 2, 2, 9, 3],
#     [7, 2, 3, 2, 1, 3, 1],
#     [1, 1, 3, 1, 7, 1, 2],
#     [4, 1, 2, 3, 4, 1, 3],
#     [3, 3, 1, 2, 3, 4, 1],
#     [1, 5, 2, 9, 4, 7, 0]]

cache = [[-1]*n for _ in range(n)]

def jump(r, c):
    global n, board, cache
    if r >= n or c >= n: return 0
    if r == n-1 and c == n-1: return 1
    if cache[r][c] != -1: return cache[r][c]
    steps = board[r][c]
    ret = jump(r+steps, c) or jump(r, c+steps)
    cache[r][c] = ret
    return ret

if jump(0, 0) == 1:
    print('Yes')
else:
    print('No')

책에서도 그래프로 모델링시, 아주 간단한 문제가 된다고 하니 이 문제의 경우에는 dfs 그래프 문제로 해결하면 될듯