[알고스팟] 보글게임

algospot.com :: BOGGLE

해설

문제에서 적힌것과 같이 dp로 푸는 대표적인 문제이다.

문제와 부분문제의 개념에 대해 알아야 한다

 

나는 다음과 같이 정리했다

 

문제 : 문제에 주어지는 문제

부분문제 : 주어진 문제의 input에서 조각내어 input을 사용하는 문제

 

가령 인풋이 abcdef 가 들어왔다 하면, a를 빼면 bcdef 이렇게 조각내서 풀면 그게 부분문제 이다

 

부분문제로 완전탐색을 만들면 dp로 변환하기가 몹시 편리하다

 

 

 

 

1. 완전 탐색으로 풀기

아래 코드로 하면 시간 초과가 난다

 

 import sys
 sys.setrecursionlimit(10**9)
 C = int(input())
 map = None
 xi = [-1,  0,  1, 1, 1, 0, -1, -1]
 yi = [-1, -1, -1, 0, 1, 1,  1,  0]
 def dfs(x,y,str):
     if x <0 or y<0 or x>4 or y>4:
         return False
     if len(str) == 0:
         return False
     if map[x][y] == str[0] and len(str) ==1:
         return True

     answer = False
     if map[x][y] == str[0]:
         for i in range(8):
             nX = x + xi[i]
             nY = y + yi[i]
             answer |= dfs(nX,nY,str[1:])
     return answer


 for _ in range(C):
 	map = []
     for i in range(5):
         map.append(sys.stdin.readline().rstrip())
     print(map)
     N = int(input())

     for _ in range(N):
         str = input()
         result = False
         for i in range(5):
             for j in range(5):
                 result |= dfs(i,j,str)
         print(str + (" YES" if result else " NO"))

 

 

2. 동적계획법으로 풀기

허나 위 문제는 부분문제를 이용하여 완전탐색을 만들었기에 dp로 변환하기가 몹시 쉽다.

 

상태값은 xy좌표와 부분문제의 수행하는 index 순서를 이용하였다.

 

import sys
sys.setrecursionlimit(10**9)
C = int(input())
map = None
xi = [-1,  0,  1, 1, 1, 0, -1, -1]
yi = [-1, -1, -1, 0, 1, 1,  1,  0]
dp = [[[-1 for _ in range(10)] for _ in range(5)] for _ in range(5)]
str = ""


def dfs(x, y, index):

    if x < 0 or y < 0 or x > 4 or y > 4:
        return False
    if len(str) == index:
        return False
    if map[x][y] != str[index]:
        return False
    if dp[x][y][index] != -1:
        return dp[x][y][index]
    if map[x][y] == str[index] and len(str) - 1 == index:
        dp[x][y][index] = True
        return dp[x][y][index]
    dp[x][y][index] = False
    for i in range(8):
        nX = x + xi[i]
        nY = y + yi[i]
        dp[x][y][index] |= dfs(nX, nY, index+1)
    return dp[x][y][index]


for _ in range(C):
    map = []
    for i in range(5):
        map.append(sys.stdin.readline().rstrip())
    N = int(input())

    for _ in range(N):
        str = input()
        dp = [[[-1 for _ in range(10)] for _ in range(5)] for _ in range(5)]
        result = False
        for i in range(5):
            for j in range(5):
                result |= dfs(i, j, 0)
        print(str + (" YES" if result else " NO"))