1890번 : 점프

 

문제링크

 

문제

N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다.

각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 한다.

가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 이동할 수 있는 경로의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 오른쪽 아래 칸에는 항상 0이 주어진다.

출력

가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 문제의 규칙에 맞게 갈 수 있는 경로의 개수를 출력한다. 경로의 개수는 263-1보다 작거나 같다.

 

 

 

 

 

 

---

 

 

DFS에 비용(cost)가 주어진 문제입니다.

간단해보이지만 예외처리를 해줘야 하는 부분이 많이 있습니다

일단 단순 DFS로 표현해보았습니다.

문제에서 오른쪽과 아래로만 이동하라고 했으니 dir는 두개만 필요했습니다.

또한 종착점이 아닌데 0이 주어지는 경우도 있는데, 이를 예외처리하지않으면 무한루프를 돌게 되어 메모리초과를 발생시킵니다.

 

 

---

 

#include<iostream>

using namespace std;

 

int data[110][110];

int dir[2][2] = { { 1, 0 }, { 0, 1 } };

int ans = 0;

int n;

 

void dfs(int row, int col){

if (data[row][col] == 0){

if (row == n - 1 && col == n - 1){

ans++;

return;

}

}

for (int i = 0; i < 2; i++){

int gorow = row + dir[i][0] * data[row][col];

int gocol = col + dir[i][1] * data[row][col];

if (gorow >= 0 && gocol >= 0 && gorow < n && gocol < n){

dfs(gorow, gocol);

 

}

}

}

 

 

 

int main(){

cin >> n;

for (int i = 0; i < n; i++){

for (int j = 0; j < n; j++){

scanf("%d", &data[i][j]);

 

}

}

 

cout << dfs(0,0) << endl;

 

}

---

 

 

 

 

각 칸을 직접 시뮬레이션하면서 모두 돌아보았으나.. 시간초과

 

경로의 개수는  263-1 보다 작거나 같다고 했으므로, long long int를 사용하여 값을 저장해야한다는 것을 알 수 있습니다.

그리고 이미 방문했었던 칸은 미리 저장해두고, 바로 빼서 쓰면 시간을 크게 단축시킬 수 있습니다.

 

 

 

소스링크