[백준] 1890번 C/C++ 풀이 _ 점프

[백준] 1890번 C/C++ 풀이 _ 점프
카테고리 Algorithm
제목 [백준] 1890번 C/C++ 풀이 _ 점프
작성시간 2018-03-01 17:38:08 +0900
조회수 473

출처 : https://www.acmicpc.net/problem/1890

시간 제한메모리 제한제출정답맞은 사람정답 비율
1 초128 MB87692537192428.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

힌트

출처

Olympiad Baltic Olympiad in Informatics BOI 2006 6번



























>> 풀이 방법

처음에 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= {10};
int round_row[2= {01};
 
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= {10};
long long round_row[2= {01};
 
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 =+ 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







▼discuss 댓글▼



▼facebook 댓글▼