백준 #1103 게임

숫자가 써져있는 보드의 맨 왼쪽 위에 돌이 있고, 그 칸에 써져있는 숫자만큼 돌을 상하좌우로 옮길 수 있습니다.  이 게임은 돌이 보드 중간에 있는 구멍 또는 밖으로 나가게 되면 끝나게 됩니다.  돌의 위치에서 판단할 때, 가장 오랫동안 돌을 움직이기 위해서는 모든 경우를 생각해야 합니다.  또는 돌이 지나왔던 칸으로 다시 돌아온다면, 그 게임을 무한하게 즐길 수도 있습니다.  난이도는 Gold I입니다.  사실 생각보다 난이도가 높습니다.  맞은 사람 548명, 정답비율 17.6%.

 

Number board game

이 문제는 모든 경우를 찾으면 반드시 시간초과로 실패하게 됩니다.  그렇다고 모든 경우를 찾지 않으면 안 됩니다.  모순이죠?  다행히 자신이 왔던 자리로 돌아오면, 사이클을 이루기 때문에 그 상태에서는 더 조사할 필요가 없습니다.  또한 이 성질은 동적 프로그래밍을 적용할 수 있는 단초가 됩니다.

 

https://www.acmicpc.net/problem/1103

1103번: 게임

모든 경우를 다 탐색하는 DFS를 이용해서 문제를 풀 수는 있습니다.  하지만, 경우의 수가 꽤 많이 나올 수 있습니다.  가로 세로 최대 50칸이 주어지기 때문에, 노드의 갯수가 2,500개짜리 그래프를 이룰 수 있습니다.  물론 이 노드들이 사이클을 이루지 않고 적절하게 이어지게 만드는 것은 어려울지 모르겠지만, 트리의 높이가 50, 각 트리의 경우의 수가 2개 이상이라고 가정하면, 2의 50승이 되기 때문에 현실적인 시간안에 계산할 수가 없습니다.  그런데 이런 상태가 되려면 반드시 어떤 노드들은 여러 경로로 들어와야 합니다.  즉, 중복이 많이 존재한다는 것입니다.  그렇기 때문에 동적 프로그래밍을 이용해야 합니다.

 

A 란 칸에 올 수 있는 경로는 여러개가 있지만, 여기서는 경로는 중요하지 않습니다.  어떤 경로로 오면 A칸에서 출발한 돌이 그 경로에 다다를 수 있습니다.  하지만, 이 경우 A 칸의 동적 프로그래밍 값에는 무한히 진행할 수 있다는 INF가 찍힐 것입니다.  그러므로 이전 경로를 마킹할 필요도 없죠.  (비트매스크를 이용한 경로 저장 방법을 사용하지 않아도 됩니다.  비트매스크를 이용한 경로 저장방법을 사용하려면, 노드의 수를 저렇게 많이 줄 수 없습니다.  저장할 수 있는 공간이 최대 128MB 정도라면, 노드갯수는 많아야 25개입니다.)

 

알고리즘은 일반적인 DFS를 이용했습니다.  

//----------------------------------------------------------
//  baekjoon #1103 - Game
//    - by Aubrey Choi
//    - created at 2019-12-30
//----------------------------------------------------------

visited[*][*] <- 0
dp[*][*] <- 0

def DFS( row, col ):
  if dp[row][col] exist: return dp[row][col]
  if current (row, col) is hole: return 0
  if visited[row][col] is set: return dp[row][col] <- INF;
  set visited[row][col]
  mex <- get Max(dfs(next row, next col) for all direction)
  reset visited[row][col]
  return dp[row][col] <- max+1