https://www.acmicpc.net/problem/14722
시간 1초, 메모리 256MB

input :

• N(1 ≤ N ≤ 1000)
• 도시의 정보 (0 : 딸기, 1 : 초코, 2 : 바나나)

output :

• 마실 수 있는 우유의 최대 개수를 출력

조건 :

• 맨 처음에는 딸기우유를 한 팩 마신다.

• 딸기우유를 한 팩 마신 후에는 초코우유를 한 팩 마신다.

• 초코우유를 한 팩 마신 후에는 바나나우유를 한 팩 마신다.

• 바나나우유를 한 팩 마신 후에는 딸기우유를 한 팩 마신다.

---

1학년 떄 교내 알고리즘 대회를 하면서 그 전 대회 문제들을 풀 때 봤던 문제이다.
그 때 부터 아주 오랫동안 풀지 않던 문제인데 드디어 해결했다.

가장 큰 문제는 DFS, BFS로는 시간제한도 걸리고 어느 지점에서 우유를 마셨는지 기록해야 해서 메모리 소모가 클 것이다.

다음 풀이

1. 시작지점의 우유 종류는 고정되어 있지 않다.
2. visit에 대한 판단
3. 우유를 마시지 않는 경우

가장 중요한 부분이다. 시작지점에서 이동하는 느낌으로 하게 된다면 시작지점에서 마시는 우유의 종류를 체크 하고 이동하는 것이 귀찮다.
도착지점 -> 시작지점으로 마실 수 있는 우유를 체킹하는 것도 하나의 방법이다.
3개의 visit을 만들던지, 3차원으로 만들던지 해서 마지막에 마신 우유가 (?)일 떄의 횟수를 저장하게 할 수 있다.

많은 if문 보다 반복문 + if문으로 가독성이 좋게 나타낼 수 있다.
prev 딕셔너리의 경우 결국 이동하는 방향은 0 -> 1, 1 -> 2, 2 -> 0 으로 우유를 마시지만 역으로 체킹을 하기 때문에

현재 위치가 0이면 그 다음은 1이 존재하는 경우의 우유 개수를 가져오고
1이면 2를, 2이면 0의 것을 가져와야 한다.

물론 시작, 도착지점의 우유 종류는 별로 중요하지 않다고 본다. 그러나 방향을 어떻게 하느냐에 따라서 반복문 안의 배열을 탐색하는 과정에서 x + 1을 사용할 것인지,
x - 1을 사용할 것인지가 정해져야 한다.

import sys

n = int(sys.stdin.readline())
graph, visit = [], [[[0] * 3 for _ in range(n + 1)] for _ in range(n + 1)]
prev = {
    0 : 1, 1 : 2, 2 : 0
}

for _ in range(n):
    temp = list(map(int, sys.stdin.readline().split()))
    graph.append(temp)

for x in range(n - 1, -1, -1):
    for y in range(n - 1, -1, -1):

        for i in range(3):
            if i == graph[x][y]:
                visit[x][y][i] = 1 + max(visit[x + 1][y][prev[i]], visit[x][y + 1][prev[i]])
            else:
                visit[x][y][i] = max(visit[x + 1][y][i], visit[x][y + 1][i])


print(visit[0][0][0])