문제가 궁금하시다면 아래의 링크를 눌러주세요!
문제 본문
접근 과정
이동하는 경우는 2차원 배열 내 좌표값만큼 오른쪽으로 가거나, 아래로 가거나 두 가지이다.
게임 판의 크기 N의 최댓값은 100이기에, 100 x 100 사이즈의 배열이라면 크게 문제가 되지 않을거라 생각해서 처음에는 단순하게 BFS식의 접근을 생각했다.
첫 풀이 시도
from collections import deque
def bfs(x, y):
global cnt
Q = deque()
Q.append([x, y])
while Q:
nx, ny = Q.popleft()
for _ in range(2):
if _ == 0:
tx, ty = nx, ny + arr[nx][ny]
else:
tx, ty = nx + arr[nx][ny], ny
if 0 <= tx < N and 0 <= ty < N:
if tx == N - 1 and ty == N - 1:
cnt += 1
else:
Q.append([tx, ty])
N = int(input())
arr = [list(map(int, input().split())) for _ in range(N)]
cnt = 0
bfs(0, 0)
print(cnt)결과는? 메모리 초과가 발생했다.
그래서 다음으로는 좌표 값을 대상으로 우/하 방향으로 이동하는 DFS 방식으로 접근하였다.
전달 인자로 넘어온 좌표 값이 (N-1, N-1)인 경우 지도의 가장 오른쪽 아래 칸에 도착한 것으로 판단하여 return문을 추가해 효율성을 조금이나마 올려서 시간 초과를 막아보려 했지만…
import sys
sys.setrecursionlimit(100000)
def dfs(x, y):
global cnt
if x == N - 1 and y == N - 1:
cnt += 1
return True
for _ in range(2):
if _ == 0:
nx, ny = x, y + arr[x][y]
else:
nx, ny = x + arr[x][y], y
if 0 <= nx < N and 0 <= ny < N:
dfs(nx, ny)
N = int(input())
arr = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
cnt = 0
dfs(0, 0)
print(cnt)결과는? 시간 초과가 발생했다!
이쯤 되니 애초에 문제에 대한 이해 자체가 잘못되었을수가 있겠구나..하는 생각이 들었고, 문제를 다시 읽어보기 시작했다.
세상에 나올 수 있는 경로의 최대 개수가 2^63 - 1개라고 한다.
이걸 보니까 내가 잘못 생각했구나… 라는 확신이 들었다.
4x4 사이즈의 배열이 있다고 가정하자
이동이 가능한 경우는 우/하 두 방향만 가능하기 때문에, 가장자리의 좌표들로 이동이 가능한 경우의 수는 한가지다.
(1,1) 좌표로 이동하려면, 아래와 같이 2가지의 경우로 이동이 가능하다.
(1,2) 좌표로 이동이 가능한 경우는 아래의 이미지와 같이 3가지다.
이러한 과정을 통해서 비약이 좀 있긴 하지만, 좌표 값들이 다 1로 채워진 nxn 사이즈의 2차원 배열에서 가장자리가 아닌 특정 좌표값 (x,y)로 이동할 수 있는 경우의 수를 아래의 이미지처럼 구할 수 있었다.
여기서 깨달은 것은 기존의 풀이로는 동일한 특정 좌표를 반복해 방문할 수 있다는 것이었고, 매 방문마다 우/하 방향으로 DFS를 돌렸기 때문에 시간초과가 발생했다는 것이었다!
DFS나 BFS로 효율성을 매우 신경써서 어떻게든 시간 제한 안에 통과시킬수도 있었겠지만, 도저히 떠오르지 않아 DP식의 풀이를 사용하기로 하였다.
import sys
def move(x, y):
for i in range(N):
for j in range(N):
if i == N - 1 and j == N - 1:
break
distance = arr[i][j]
if 0 <= distance + j < N:
dp[i][distance + j] += dp[i][j]
if 0 <= i + distance < N:
dp[i + distance][j] += dp[i][j]
input = sys.stdin.readline
N = int(input())
arr = [list(map(int, input().split())) for _ in range(N)]
dp = [[0] * N for _ in range(N)]
dp[0][0] = 1
move(0, 0)
print(dp[N - 1][N - 1])
통과!
읽어주셔서 감사합니다!
