백준_17130_토끼가 정보섬에 올라온 이유 (python)

★ 접근

 처음에는 단순하게 문제를 보고 bfs를 떠올렸다. 문제가 bfs를 떠올리게 유도했기 때문에 대부분의 사람들도 처음에 bfs를 떠올릴 수 밖에 없다고 생각한다. 그러나 구현을 하다보면 bfs로(풀 수도 있겠지만 필자는 실력이 부족해서 구현할 수가 없다) 풀기에는 쉽지 않다는 것을 떠올렸고 생각하면 할 수록 dp로 나를 이끌었다.

 

★ 풀이

1. 일단 토끼가 있던 위치를 찾아주고 해당 좌표에 dp를 0으로 처리함으로써 방문 처리를 해준다. 

2. 토끼가 있던 다음 열부터 반복을 시작한다. 다음 열부터 하는 이유는 첫째, 토끼는 앞으로만 이동하기 때문이다. 두번쨰는 앞으로만 이동하기 때문에 뒤에 상황은 볼 필요가 없다. 세번째, 방향을 반대로 ↙,↖,← 이 3가지 방향으로 생각할 것이기 때문이다.

3. 행을 어디서부터 시작할지(여기서 많이 헤맸는데) 모든 경우에 대해서 알아야하니 0부터 시작하기로 결정했다. 

4. 당근을 하나도 못 챙기고 탈출할 수도 있으니 flag로 쪽문에는 들렸다는 것을 표시했다.

5. 나머지는 문제에서 주어진대로 구현만 하면 된다

- 코드

import sys
input = sys.stdin.readline
n,m = map(int,input().split())
graph = []
sr, sc = 0,0
for i in range(n):
    temp = list(input())
    for j in range(m):
        if temp[j] == 'R':
            sr,sc = i,j
    graph.append((temp))
dp = [[-1] * m for _ in range(n)]
dp[sr][sc] = 0 
dx = [-1,0,1]
dy = [-1,-1,-1]
def isRange(r,c):
    if 0 <= r < n and 0 <= c < m:
        return True
    return False
flag = 0
count = 0
for j in range(sc+1,m): #여까지는 누구나 생각함
    for i in range(0,n):
        if graph[i][j] == '#':
            continue
        for k in range(3):
            nx = i + dx[k]
            ny = j + dy[k]
            if isRange(nx,ny) and dp[nx][ny] != -1:
                if graph[i][j] == 'C':
                    dp[i][j] = max(dp[i][j], dp[nx][ny] + 1)
                if graph[i][j] == '.':
                    dp[i][j] = max(dp[i][j], dp[nx][ny])
                if graph[i][j] == 'O': # 당근을 하나도 안 들고 탈출할 수도 있는 거잖아 그치?
                    flag = 1
                    dp[i][j] = max(dp[i][j], dp[nx][ny])
                    count = max(count, dp[i][j])
            
if flag == 0:
    print(-1)
else:
    print(count)

  - 회고

 행을 어디서 시작할지, 결국 토끼가 있는 곳에서 출발을 해서 답을 구해야하는데 이것을 어떻게 구현할지 이 두가지만 해결했으면 됐는데 이 두가지 부분에서 해결을 못했다. 문제는 재밌었는데 많이 아쉽다.... 생각할 수 있었는데..... 할수있다!!