[백준-파이썬] 17130: 토끼가 정보섬에 올라간 이유

문제 보러 가기!

문제를 읽어보니 토끼가 정보섬에 올라간 이유는! 당근을 많이 주워 가기 위해서였다 ! 🥕🥕
토끼는 →, ↘, ↗ 방향으로만 이동할 수 있다. 정문으로 들어와서 쪽문으로 나가는데, 쪽문은 여러 개이고 a 쪽문을 지나서 b 쪽문으로 나가도 상관없다. 토끼가 섬에 있을 동안 얻을 수 있는 당근의 최대 개수를 구하는 문제였다! (쪽문으로 빠져나갈 수 없는 경우에는 -1을 출력한다)

ㅠㅠㅠ 많이 틀리다가 맞았따.. ㅠㅠㅠㅠ

일단은 토끼가 정문으로 들어오는 것은 'R'로 표시되기 때문에, 그 위치를 찾았다.
그 후에는 그쪽보다 오른쪽인 지점들을 다 쭉~ 봐주었다. 그러면서 해당 지점일 때까지 얻을 수 있는 당근의 최대 개수로 업데이트했다. (그 지점으로 올 수 있는 방법은 →, ↘, ↗ 을 해서 온 것이다. 그러니까 ←, ↙, ↖ 한 지점 중에 당근 최대 수를 가지고 오는 것이다!

크게 설명하면 이것이고, 좀 더 세세한 부분은 신경써야 한다.. (이것들 때문에 많이 틀렸다..)

1. 그 지점이 벽이면, 올 수 없으니까 바로 continue했다.
2. ←, ↙, ↖ 한 지점들이 다 벽이면, 그 지점까지 못 가는 것이니까 그것도 체크해줘야 한다. ( 나는 visited, flag를 이용해서 판단했다.)
3. 그 지점이 무엇인지에 따라서 조금 다르게 해야 한다.
   1) 그 지점에 당근이 있으면, ←, ↙, ↖ 한 지점 중에 당근 최대 수에다가 1을 더해줘야 한다.
   2) 그 지점이 벽이면, 아까 말했듯이! 볼 필요가 없다.
   3) 그 지점이 쪽문이라면, 그 때 당근 최대 수를 정답 후보 리스트에 넣었다.

재미있는 문제였다

import sys

input = sys.stdin.readline
MIISS = lambda: map(int, input().strip().split())
directions = [(0, -1), (1, -1), (-1, -1)]

N, M = MIISS()
arr = list(input().strip() for _ in range(N))
dp = [[0] * M for _ in range(N)]
visited = [[False] * M for _ in range(N)]


# 토끼가 들어온 위치 찾기
def find_a_rabbit_start():
    for i in range(N):
        for j in range(M):
            if arr[i][j] == 'R':
                return (i, j)


ri, rj = find_a_rabbit_start()
side_doors = []
visited[ri][rj] = True

for j in range(rj + 1, M): # 왼쪽으로는 못 가니까 ri+1부터 보기
    for i in range(N):
        if arr[i][j] == '#':
            continue  # 벽이면 넘어가기

        # 그 지점으로 올 수 있는 세 지점 중 당근 수 젤 많은 것
        most_carrot_spot = 0
        flag = False # 그 지점까지 갈 수 있는지 체크

        for ki, kj in directions:
            ni, nj = i + ki, j + kj
            if 0 <= ni < N and 0 <= nj < M and visited[ni][nj]:  # 그 지점으로 올 수 있는 세 지점 - 범위 체크, 방문한 적이 있어야 함! ( 다 벽이면 못 감)
                most_carrot_spot = max(most_carrot_spot, dp[ni][nj])
                flag = True

        if flag == False: # 다 벽이면 못가는데, 갈 수 있다는 뜻
            continue

        visited[i][j] = True # 그 지점에 갈 수 있다는 뜻이니까 방문 체크 !

        if arr[i][j] == 'C':
            dp[i][j] = most_carrot_spot + 1

        elif arr[i][j] == '.':
            dp[i][j] = most_carrot_spot

        elif arr[i][j] == 'O':
            if most_carrot_spot == -1:  # 여기까지 도달하지 못했으면
                continue
            dp[i][j] = most_carrot_spot
            side_doors.append(most_carrot_spot)

# 쪽문으로 나갈 수 있으면
if side_doors:
    print(max(side_doors))
else:  # 불가능
    print(-1)