BOJ 14722 우유 도시

시간 1초, 메모리 256MB
input :

• N (1<= N <= 1,000)

• 도시의 정보가 주어짐 (0 딸기우유만, 1 초코우유만, 2 바나나우유만)
  output :

• 마실 수 있는 우유의 최대 개수
  조건 :

• 딸기 -> 초코 -> 바나나 -> 딸기 순서로 우유 마심.

• 동쪽(우), 남쪽(하)로만 움직인다.

---

이동할때에 꼭 0, 1, 2 순서로 움직이는 것은 아님.
시작지점은 언제나 0이고.
우유를 마신 횟수 의 나머지 연산을 이용해서 다음 먹을 우유를 찾는 것이 좋을 것 같다.
이동 할 지점을 큐에 넣고 현재 지점이 나머지 연산을 한 값과 같으면 우유 개수 올리기.

현재의 위치에서 이동할 위치에 정답[현재의 위치] % 3 값이 존재 할 경우 순서대로 우유를 마시고 있는 것이다.

if graph[nx][ny] == answer[x][y] % 3:

이것을 계속 반복.

import sys
sys.setrecursionlimit(10000)

N = int(input())
graph = []
answer = [[0] * N for _ in range(N)]
for _ in range(N):
    graph.append(list(map(int, input().split())))
answer[0][0] = 1

def DFS(x, y):
    dy = [1, 0]
    dx = [0, 1]
    for i in range(2):
        nx = x + dx[i]
        ny = y + dy[i]
        if ny >= N or nx >= N:
            continue
        if graph[nx][ny] == answer[x][y] % 3:
            answer[nx][ny] = max(answer[nx][ny], answer[x][y] + 1)
        DFS(nx, ny)
DFS(0, 0)
print(answer[N - 1][N - 1])

시간초과 어떻게 해야 하누..