출처 : https://www.acmicpc.net/problem/1890
점프 실패 풀이
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 8769 | 2537 | 1924 | 28.088% |
문제
N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다.
각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 한다.
가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 이동할 수 있는 경로의 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 오른쪽 아래 칸에는 항상 0이 주어진다.
출력
가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 문제의 규칙에 맞게 갈 수 있는 경로의 개수를 출력한다. 경로의 개수는 263-1보다 작거나 같다.
예제 입력
4 2 3 3 1 1 2 1 3 1 2 3 1 3 1 1 0
예제 출력
3
힌트
출처
>> 풀이 방법
처음에 bfs 를 이용해서 문제를 풀었다.
하지만, 메모리와 시간 초과 문제가 발생한다.
N 이 100 이 들어오고 (99,99) 번째 항목이 0이고 나머지 모든 항목이 1이 들어온다고 가정하면,
queue 에 너무 많은 숫자가 들어가서 시간 초과와 메모리 초과 문제가 발생하게 된다.
답이 가령 230이라고 하면, bfs 를 이용하면 해당 경로를 따로따로 모두 지나야 하기 때문이다.
따라서, 위 문제는 bfs, dfs 로 풀면 안되고, 오른쪽과 아래로 밖에 갈 수 없기 때문에 경로의 갯수를 저장하는 배열을 생성하여
이중 포문을 사용하여 (0,0)->(0,1)->(0,2)..... ->(1,0)->(1,1) ..... 와 같은 순서로 돌면서,
가능한 경로의 갯수를 계속 더해주는 방법이 가장 효율적이다.
교훈 : 미리미리 시간이나 공간 복잡도를 철저하게 계산하고 접근해야겠다.
>> 틀린 소스 코드 ( 메모리와 시간 초과 발생 )
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 | #include <iostream> #include <queue> using namespace std; int N; int** arr; int answer = 0; typedef struct POSITION{ int row; int col; }POSITION; queue<POSITION*> bfs_queue; int round_col[2] = {1, 0}; int round_row[2] = {0, 1}; void addQueue(POSITION* now_position) { int move_val = arr[now_position->row][now_position->col]; for (int i = 0; i < 2; i++) { int sub_row = now_position->row + move_val * round_row[i]; int sub_col = now_position->col + move_val * round_col[i]; if ((0 <= sub_row) && (sub_row < N) && (0 <= sub_col) && (sub_col < N)) { POSITION* sub_posi = (POSITION*)malloc(sizeof(POSITION)); sub_posi->row = sub_row; sub_posi->col = sub_col; bfs_queue.push(sub_posi); } } } // stack 을 이용하여 구현해보자 void bfs() { POSITION* sub_posi = (POSITION*)malloc(sizeof(POSITION)); sub_posi->row = 0; sub_posi->col = 0; addQueue(sub_posi); while (bfs_queue.size()) { sub_posi = bfs_queue.front(); bfs_queue.pop(); if (!arr[sub_posi->row][sub_posi->col]) { if ((sub_posi->row == N - 1) && (sub_posi->col == N - 1)) answer++; } else { addQueue(sub_posi); } free(sub_posi); } } int main() { cin >> N; arr = (int**)malloc(sizeof(int*)*N); for (int i = 0; i < N; i++) arr[i] = (int*)malloc(sizeof(int)*N); for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { scanf("%d", &arr[i][j]); } } bfs(); cout << answer; return 0; } | cs |
>> 정답 소스 코드
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 | #include <iostream> using namespace std; int N; long long** arr; long long** route_num_arr; long long round_col[2] = {1, 0}; long long round_row[2] = {0, 1}; int main() { cin >> N; arr = (long long**)malloc(sizeof(long long*)*N); route_num_arr = (long long**)malloc(sizeof(long long*)*N); for (int i = 0; i < N; i++) { arr[i] = (long long*)malloc(sizeof(long long)*N); route_num_arr[i] = (long long*)malloc(sizeof(long long)*N); } for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { scanf("%lld", &arr[i][j]); route_num_arr[i][j] = 0; } } route_num_arr[0][0] = 1; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if ((arr[i][j]) && (route_num_arr[i][j])) // 현재 위치에 대하여 오른쪽, 아래 값 추가 for (int k = 0; k< 2; k++) { int sub_row = i + arr[i][j] * round_row[k]; int sub_col =j + arr[i][j] * round_col[k]; if ((sub_row < N) && (sub_col < N)) { route_num_arr[sub_row][sub_col] += route_num_arr[i][j]; } } } } cout << route_num_arr[N-1][N - 1] << endl; return 0; } | cs |