알고리즘/BOJ
[BOJ 17489, Python 3] 보물 찾기
70825
2021. 9. 1. 19:58
반응형
https://www.acmicpc.net/problem/17489
17489번: 보물 찾기
(1, 1) - (1, 2) - (1, 3) - (1, 4) - (2, 4) - (3, 4) 로 이동하며, (3, 4) 지점으로부터 “ABC”를 더 이상 찾아갈 수 없어 문자열 “ABC”를 2번 따라간 곳에 보물이 있다고 생각한다.
www.acmicpc.net
풀이
문제에서 중복된 알파벳이 주어지지 않는다고 했으므로 사이클이 생기는 경우는 무조건 마지막 문자열 다음 첫번째 문자열이 오는 경우입니다. 이 부분을 만나면 -1을 출력해주고 종료해주시면 됩니다.
사이클을 확인하는 방법은 DFS를 하면서 visit[x][y] = 1을 해주다가 해당 노드보다 더 뒤로 돌아가게 될 경우엔 visit[x][y] = 0으로 바꿔주시면 됩니다.
제한 값들이 충분히 크고, 알파벳 중복도 가능하다면 이미 한 번 갔던 경로는 앞으로 문자열이 몇 번 반복되는지 알 수 있으니까 DP를 사용해야되서 높은 난이도가 될 것 같은데, DFS만으로도 통과할 수 있어서 플레 문제는 아닌 것 같네요.
코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
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)
|
cs |
반응형