[BOJ 17489, Python 3] 보물 찾기

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

17489번: 보물 찾기

 

 

풀이

문제에서 중복된 알파벳이 주어지지 않는다고 했으므로 사이클이 생기는 경우는 무조건 마지막 문자열 다음 첫번째 문자열이 오는 경우입니다. 이 부분을 만나면 -1을 출력해주고 종료해주시면 됩니다.

사이클을 확인하는 방법은 DFS를 하면서 visit[x][y] = 1을 해주다가 해당 노드보다 더 뒤로 돌아가게 될 경우엔 visit[x][y] = 0으로 바꿔주시면 됩니다.

 

제한 값들이 충분히 크고, 알파벳 중복도 가능하다면 이미 한 번 갔던 경로는 앞으로 문자열이 몇 번 반복되는지 알 수 있으니까 DP를 사용해야되서 높은 난이도가 될 것 같은데, DFS만으로도 통과할 수 있어서 플레 문제는 아닌 것 같네요.

 

 

코드

def go(x, y, size, val):
    global ans
    visit[x][y] = 1
    if size % len(s) == 0 and val > ans[0]: ans = [val, x, y]
    for i in range(4):
        nx, ny = x+dx[i], y+dy[i]
        if 0 <= nx < n and 0 <= ny < m and MAP[nx][ny] == s[size % len(s)]:
            if visit[nx][ny] and size % len(s) == 0: print(-1); exit()
            go(nx, ny, size + 1, val if size % len(s) else val + 1)
    visit[x][y] = 0
 
import sys
sys.setrecursionlimit(100000)
dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]
n, m, l = map(int, input().split())
s = input()
MAP = [input() for _ in range(n)]
visit = [[0] * m for _ in range(n)]
ans = [-1, -1, -1]
go(0, 0, 1, 1)
if ans[0] != -1:print(f'{ans[0]}\n{ans[1]+1} {ans[2]+1}')
else: print(-1)