반응형
1103번: 게임
줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는
www.acmicpc.net
import sys
sys.setrecursionlimit(10**6)
dr = [0, 1, 0,-1]
dc = [1, 0,-1, 0]
def dfs(r ,c):
global state, visited
if not(0<=r<N and 0<=c<M) or board[r][c] == 'H':
return 0
if visited[r][c]:
state = True
return -1
if dp[r][c] != -1:
return dp[r][c]
visited[r][c] = True
X = int(board[r][c])
for i in range(4):
dp[r][c] = max(dp[r][c], dfs(r+dr[i]*X, c+dc[i]*X)+1)
if state:
return -1
visited[r][c] = False
return dp[r][c]
if __name__ == '__main__':
N, M = map(int, input().split())
board = [input() for _ in range(N)]
visited = [[False]*M for _ in range(N)]
dp = [[-1]*M for _ in range(N)]
state = False
print(dfs(0,0))
위 문제는
DFS(Depth-First Search, 깊이 우선 탐색)와
DP(Dynamic Programming, 동적계획법)을 이해해야합니다.
DP에 대한 내용은 아래와 같습니다.
velog.io/@chelsea/1-%EB%8F%99%EC%A0%81-%EA%B3%84%ED%9A%8D%EB%B2%95Dynamic-Programming-DP
[자료구조와 알고리즘] 동적 계획법(Dynamic Programming, DP)
동적 계획법(Dynamic Programming) - 컴퓨터 공학 스터디 W1 자료구조와 알고리즘 내용에 앞서 학교에서 컴퓨터 공학 이론 스터디를 진행하고 있습니다. 매주 발표하는 내용을 시리즈로 업로드할 예정
velog.io
반응형