[Python] 5011번 Robots on a grid

https://www.acmicpc.net/problem/5011

5011번: Robots on a grid

---

 

22/10/14

 

 

전형적인 BFS문제에 갈 수 있는 방법을 구하는 DP문제가 더해진 문제로, 개인적으로 골드 5가 적당한 난이도라고 생각이 든다.

---

 

문제 접근 방식:

 

 

외국어 문제이기 때문에 문제 요약을 하자면 다음과 같다.

 

그래프가 주어지면, 로봇이 오른쪽으로 가는 것과 아래로 가는 것만을 이용하여 왼쪽 맨 위에서 오른쪽 맨 아래로 갈 수 있다면, 갈 수 있는 방법의 수를 출력하는 문제이다.

 

만약 두 방향을 이용해 갈 순 없지만 네 방향 모두를 사용하여 갈 순 있다면, THE GAME IS LIE를 출력하고, 어떻게 해서든 도달하지 못한다면, INCONCEIVABLE을 출력하면 된다.

 

일단, 문제에서 주어진 그대로, 먼저 4방향 BFS를 진행하여, INCONCEIVABLE을 출력할지 말지의 여부를 결정했다.

 

이후 2방향 BFS를 진행하여 THE GAME IS LIE를 출력할지 말지의 여부를 결정했다.

 

만약 2방향으로 갈 수 있다고 나왔다면, 주어진 그래프를 사용하여 DP를 짰다.

 

이때, DP식은 다음과 같다.

 

$$DP[i][j] = i번째 줄의 j번째 칸을 갈 수 있는 방법의 수$$

 

 

만약 "i번째 줄의 j번째 칸" 위의 칸도 갈 수 있는 칸이고, 왼쪽 칸도 갈 수 있는 칸이라면, 위에서 내려오는 경우의 수와 왼쪽에서 해당 칸으로 가는 경우의 수를 더해서 DP식이 다음과 같을 것이다.

 

 

$$DP[i][j] = DP[i-1][j] + DP[i][j-1]$$

 

 

만약 위의 칸이 막혀있는 경우라면, 

 

 

$$DP[i][j] = DP[i][j-1]$$

 

 

만약 왼쪽 칸이 막혀있는 경우라면,

 

 

$$DP[i][j] = DP[i-1][j]$$

 

 

만약 두 칸이 모두 막혀있는 경우라면,

 

 

$$DP[i][j] = 0$$이 될 것이다.

 

 

이를 감안하여 경우의 수를 구하면 된다.

 

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 5011번 Robots on a grid
# DP, 그래프 이론, 그래프 탐색, BFS
'''
접근 방법:
먼저 맨 왼쪽 위칸에서 맨 오른쪽 아래칸으로 갈 수 있는지 4방향 BFS 탐색한다.
만약 탐색할 수 없다면 INCONCEIVABLE을 출력하자.
만약 탐색 가능하다면, 오른쪽으로 움직이는 것과 아래로 움직이는 것만을 사용하여(2방향)
탐색할 수 있는지 확인한다.
불가능 하다면 THE GAME IS A LIE를 출력하자.
가능하다면 DP로 경우의 수를 출력하자.
'''
import sys
from collections import deque
input = sys.stdin.readline
MOD = 2**31 - 1

N = int(input())
graph = [list(input().rstrip()) for _ in range(N)]
visited = [[0 for _ in range(N)] for _ in range(N)]
dc = [1, 0, -1, 0]
dr = [0, 1, 0, -1]

queue1 = deque()
queue1.append((0, 0))
visited[0][0] = 1
while queue1:
    row, col = queue1.popleft()
    for i in range(4):
        now_r, now_c = row + dr[i], col + dc[i]
        if 0 <= now_r < N and 0 <= now_c < N and visited[now_r][now_c] != 1 and graph[now_r][now_c] != '#':
            visited[now_r][now_c] = 1
            queue1.append((now_r, now_c))

if visited[N-1][N-1]: # 4방향 탐색으로 도달 가능 하다면
    visited = [[0 for _ in range(N)] for _ in range(N)]
    queue2 = deque()
    queue2.append((0, 0))
    visited[0][0] = 1
    while queue2:
        row, col = queue2.popleft()
        for i in range(2):
            now_r, now_c = row + dr[i], col + dc[i]
            if 0 <= now_r < N and 0 <= now_c < N and visited[now_r][now_c] != 1 and graph[now_r][now_c] != '#':
                visited[now_r][now_c] = 1
                queue2.append((now_r, now_c))
    
    if visited[N-1][N-1]: # 2방향 탐색으로 도달 가능하다면
        DP = [[1 for _ in range(N)] for _ in range(N)]
        for k in range(2*N-1):
            for s in range(k+1):
                row, col = s, k-s
                try:
                    if graph[row][col] == '#':
                        DP[row][col] = 0
                    else:
                        if row == k:
                            DP[row][col] = DP[row-1][col]
                        elif col == k:
                            DP[row][col] = DP[row][col-1]
                        else:
                            DP[row][col] = (DP[row-1][col] + DP[row][col-1]) % MOD
                except IndexError:
                    continue
        print(DP[N-1][N-1])
    else:
        print('THE GAME IS A LIE')
else:
    print('INCONCEIVABLE')