[백준] (dp) 숨바꼭질 201101

 

www.acmicpc.net/problem/1890

1890번: 점프

1. 문제 설명

 

 

 

2. 풀이 

 

전형적인 DP 문제인데.. 문제를 착각하고 DFS 로 풀어버렸다. 

 

 

1) 오답 

### dp 로 풀어

### DFS


from collections import deque
import sys

next_point = deque([(0,0)])
hist_set = set()
matrix = []
black_list = set()
N = int(input())
for idx in range(N):
    matrix.append(list(map(int, sys.stdin.readline().split())))

def dfs(x,y,matrix):

    now_val =  matrix[x][y]
    # print(x, y,"now",now_val)
    out_of_range = 0

    if 0 <= x + now_val < N :
        if matrix[x + now_val][y] == 0:
            # print("YES")
            return 1
        else:
            next_point.append((x + now_val, y))
    else:
        out_of_range +=1

    if 0 <= y + now_val < N :
        if matrix[x][y + now_val] == 0:
            # print("YES")
            return 1
        else:
            next_point.append((x, y + now_val))
    else:
        out_of_range +=1

    if out_of_range == 2:
        black_list.add((x,y))
    return 0

def solution(next_point,N, black_list, matrix):
    cnt = 0
    while next_point:
        x,y = next_point.pop()
        if (x,y) not in black_list:
            cnt += dfs(x, y, matrix)
            # print(next_point)
        else:
            continue
    return cnt

print(solution(next_point,N, black_list, matrix))

 

 

3. 다시 수정한 DP 코드 

import sys
N = int(sys.stdin.readline())
board = []
for i in range(N):
    temp = list(map(int, sys.stdin.readline().split()))
    board.append(temp)
 
dp = []
for i in range(N):
    dp.append([])
    for j in range(N):
        dp[i].append(0)
 
dp[0][0] = 1
for i in range(N):
    for j in range(N):
        if i==N-1 and j==N-1:
            break
        value = board[i][j]
        down = i + value
        right = j + value
 
        if down < N:
            dp[down][j] += dp[i][j]
        if right < N:
            dp[i][right] += dp[i][j]
 
print(dp[N-1][N-1])