흙금이네 블로그

아이디어 동적 계획법과 DFS로 동전을 더 이동할 수 없는 곳에서부터 이동할 수 있는 최대 횟수를 구해 나간다. 풀이 람다식으로 입력으로 주어지는 문자열에서 H는 0으로, 나머지는 정수형으로 바꾼 리스트를 리스트 board에 저장한다. 각 칸의 동전 최대 이동 횟수를 저장하는 2차원 리스트 dp와 각 칸의 방문 여부를 표시하는 2차원 리스트 visited를 만든다. 가장 왼쪽 위칸의 행, 열, 이동 칸 수를 인자로 함수 dfs를 호출한다. 함수 dfs에서는 현재 칸을 이미 방문하여 최대 이동 횟수가 dp에 저장되어 있으면 해당 값을 반환하여 종료한다. dp에 저장되어 있지 않으면 최대 이동 횟수를 저장하는 move에 1을 저장하고, visited에 방문 표시를 한다. 보드의 범위를 벗어나지 않고 이동할 ..