https://www.acmicpc.net/problem/1987
시간 2초, 메모리 256MB
input:
- R C (1 <= R, C <= 20)
- 대문자 알파벳들이 R번 입력.
output :
- 말이 이동할 수 있는 최대의 칸 수를 출력.
조건 :
- 좌측 상단 에는 출발하는 말이 놓여 있다.
- 말으 상하좌우 로 이동 / 적혀 있는 알파벳이 지금까지 지나온 알파벳과는 달라야 한다.
- 한번도 만난 적 없는 알파벳으로만 이동할 수 있다.
현재 까지의 알파벳을 기록 해야 함. 최대 거리를 기록 해야 하니 DFS로 하는게 맞을거 같음.
알파벳을 기록하는 리스트, visit 리스트.
재귀의 기저 사례
- 이동하려는 좌표가 격자의 바깥인 경우.
- 현재 좌표의 알파벳에 이미 와본 경우.
- 알파벳을 기록하는 리스트의 경우 DFS를 실행할 때 마다 초기화가 필요함.
- visit이 필요한가??? 이미 다녀간 곳을 다시 간다면 그 알파벳은 왔던 것을 표시했는데...
- 재귀의 리턴값... 은 최댓값이 되어야 한다...
그냥 알파벳 봤는지 기록하는 1차원 리스트 만들면 끝 아닌가? 어차피 최대 이동은 알파벳 숫자 만큼이니까.
현재 위치한 곳의 알파벳이 무엇인지 알아야 함.
흠.. 시간 초과가 나는데 어떻게 해야 할까????
아니네.. pypy3로 제출하니까 그냥 틀렸네.. 어디일까..
dp로 값을 기록 하며 하는 것은 틀렸다고 함.. 아 중복되어서 계산 될수도 있겠군. 여러번 겹쳐지니까....
전역변수 ans를 이용해서 최댓값을 갱신하는 방법으로 하는 것이 옳다.
정답 코드 :
import sys
R, C = map(int, sys.stdin.readline().split())
graph = [[] for i in range(R)]
alpha = [0] * (26)
ans = 0
for i in range(R):
data = sys.stdin.readline().strip()
for j in range(len(data)):
graph[i].append(ord(data[j]) - 65)
def DFS(x, y, cnt):
global ans
ans = max(ans, cnt)
dx = [1, -1, 0, 0]
dy = [0, 0, -1, 1]
for i in range(len(dx)):
nx = x + dx[i]
ny = y + dy[i]
if nx >= R or nx < 0 or ny < 0 or ny >= C:
continue
if not alpha[graph[nx][ny]]:
alpha[graph[nx][ny]] += 1
DFS(nx, ny, cnt + 1)
alpha[graph[nx][ny]] -= 1
alpha[graph[0][0]] = 1
DFS(0, 0, 1)
print(ans)
