[BOJ 백준] 1513번 : 경로 찾기 (C++)

[BOJ 백준] 1513번 : 경로 찾기 (C++)

목차

• 01. 개요
• 02. 접근 방식
• 03. 정답 코드
• 04. 마무리

---

01. 개요

출처

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

 

문제

 

입력

 

출력

 

예시

 

 

---

02. 접근 방식

요약

1. 위치마다 현재까지 방문한 오락실 번호와 오락실 방문 횟수에 대한 정보를 소유

2. 현재 위치에 오락실이 존재할 때, 현재 오락실 번호보다 작은 오락실의 기록만 위쪽과 왼쪽에서 가져오기

3. 계산할 때마다 1'000'007의 나머지 값으로 저장

4. 시뮬레이션이 끝난 후, 마지막 위치에서 같은 방문 횟수를 가진 데이터끼리 더하고 출력

과정

먼저, 데이터를 어떻게 저장할 것인가에 대해 고민했습니다.

가로 길이와 세로 길이는 최대 50입니다.

또한, 오락실의 최대 개수도 50개입니다. 그러므로, 오락실 최대 방문 횟수도 50번입니다.

이를 시간적 측면과 공간적 측면으로 나눠서 보겠습니다.

 

50을 4번 곱하면, 6'250'000입니다.

즉, 시간제한인 2초 내로 해결할 수 있는 크기입니다.

 

메모리 측면으로 보면, 각 경우에 대해서 약 100만의 나머지 값으로 관리합니다.

따라서, int형으로 저장할 수 있기에, 위 값인 약 600만에서 4byte를 곱합니다.

25'000'000 byte ≒ 25'000KB ≒ 25MB로, 메모리 제한인 128MB 내에서 해결할 수 있습니다.

 

배열[y 좌표][x 좌표][오락실 번호][오락실 방문 횟수]

따라서, 4차원 배열로 방문 경우를 계산하겠습니다. (3차원 배열로 해결하는 방법도 있습니다!)

 

여기서 추가로 오락실 번호와 방문 횟수에 따른 데이터 처리가 필요합니다.

이를 간단한 예시를 통해서 알아보겠습니다.

 

네모 안에 적힌 숫자는 오락실 번호를 의미합니다.

1번 오락실을 방문할 수 있는 위치 해당 오락실을 기준으로 왼쪽과 위쪽입니다.

두 위치를 방문할 수 있는 경우는 방문 횟수가 0번일 때, 1개만 존재한다고 가정합니다.

 

기존 데이터는 모두 오락실 방문 횟수가 0번입니다.

현재 위치에 도달할 때, 방문 횟수를 1 증가한 1번에 데이터를 추가해야 합니다.

그리고, 현재 오락실 번호가 1번이므로, [y][x][1][1]에 데이터를 저장해야 합니다.

따라서, 계산을 마치면, 위 사진과 같은 결과가 나오게 됩니다.

 

 

해당 과정으로 예제 1번을 한 단계씩 계산해 보겠습니다.

먼저, 시작 위치에 오락실이 없으므로 [오락실 번호 0번][방문 횟수 0번]에 1로 초기화를 합니다.

 

 

진행 방향은 오른쪽으로 검사를 하고, 한 행 검사가 완료되면, 다음 행으로 넘어갑니다.

  

첫 번째 행은 오른쪽으로 이동만 가능하므로, 오락실이 없으면, 기존 경우를 그대로 물려받습니다.

그다음 검사 위치는 0번째 열입니다. 0번째 열은 아래로만 이동할 수 있으므로, 오락실이 없을 때, 기존 경우를 그대로 물려받습니다.

 

 

그 후, 오락실 1번에 도달하는 경우입니다.

오락실을 방문할 수 있는 경우는, 현재 오락실 번호보다 작은 곳에서만 방문할 수 있습니다.

그래서, 이전에 방문하지 않은 경우에만, 1번 오락실에 도달할 수 있습니다.

따라서, [1번 오락실][1번 방문]에 2를 추가합니다.

 

그다음 위치에는 오락실이 존재하지 않습니다.

그래서, 기존 경우를 그대로 물려받습니다.

 

2번 오락실에 방문하는 경우는 두 가지가 있습니다.

1. 오락실을 방문하지 않고, 바로 2번 오락실에 방문하기

2. 1번 오락실을 방문하고, 2번 오락실을 방문하기

 

그래서, 이를 토대로 계산하면 다음과 같습니다.

1. 왼쪽에서는 방문 횟수 0이므로 1번 조건을 만족합니다. 그래서, 해당 데이터를 [2번 오락실][1번 방문]에 추가합니다.

2. 위쪽에서는 방문 횟수가 1이므로 2번 조건을 만족합니다. 그래서, 해당 데이터를 [2번 오락실][2번 방문]에 추가합니다.

 

마지막 경우는 오락실이 아니므로 기존 데이터를 그대로 물려받습니다.

 

따라서, 마지막에 도달하는 경우는 다음과 같습니다.

이를 방문 횟수별로 묶으면, 아래와 같습니다.

1. 방문 횟수 0번 : 1회

2. 방문 횟수 1번 : 3회

3. 방문 횟수 2번 : 2회

 

주의점

1. 위치에 따라 배열 경계 밖에 접근하지 않도록 주의해야 합니다.

 

0행은 오른쪽으로만 이동이 가능합니다.

0열을 아래쪽으로만 이동이 가능합니다.

 

 

 

---

03. 정답 코드

// 골드 2 - 1513번 : 경로 찾기
// 작성자 : free4760(jeonghoe22)

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>

using namespace std;

// N*M (각 1~50)
// 세준이네 집 위치 1,1 -> 학원 N,M

// 오락실 개수 C -> (0~50)
// 오락실 위치 중복 x
// 오락실 번호는 증가하는 순서대로만 갈 수 있음.
// 2번 오락실 : x -> 2번 or x -> 1번 -> 2번

// 이동 : 아래와 오른쪽만 가능
// 오락실 0개 방문부터 C번 방문까지 모두 출력
// 경우의 수는 1'000'007을 나머지 연산해서 출력

// N*M = 2'500
// 오락실 개수 : *50 = 125'000
// 오락실 방문 개수 : *50 = 6'250'000 -> 24MB

// 오락실 번호(50) * 방문 횟수(50)
// 오락실에 방문하면, 해당 오락실 번호의 방문 횟수 + 1해서 옮기기
// 같은 방문 횟수와 오락실 번호끼리 더하기
// 마지막에 방문 횟수끼리 묶어서 출력

const int DIV = 1'000'007;

struct Area
{
    int idx = 0;
    vector<vector<int>> vec;
    
    Area()
    {
        vec = vector<vector<int>>(51, vector<int>(51, 0));
    }
};

vector<vector<Area>> g_areas;

// 오락실 위치 입력
void inputInfo(const int N, const int M, const int C)
{
    g_areas = vector<vector<Area>>(N, vector<Area>(M));

    int y, x;
    for(int i = 1; i <= C; i++)
    {
        cin >> y >> x;
        g_areas[y-1][x-1].idx = i;
    }
}

// 시뮬레이션
void simulate(const int N, const int M, const int C)
{
    // 첫 위치 설정
    int idx = g_areas[0][0].idx;
    int tmp = (int)(idx > 0);
    g_areas[0][0].vec[idx][tmp] = 1;

    // y
    for(int y = 0; y < N; y++)
    {
        // x
        for(int x = 0; x < M; x++)
        {
            idx = g_areas[y][x].idx;

            // 오락실 번호
            for(int num = 0; num <= C; num++)
            {
                // 오락실 방문 횟수
                for(int cnt = 0; cnt <= C; cnt++)
                {
                    // 오락실이 없는 경우
                    if(idx == 0)
                    {
                        // 위쪽에서 가져오기 가능
                        if(y != 0)
                            g_areas[y][x].vec[num][cnt] += g_areas[y-1][x].vec[num][cnt];

                        // 왼쪽에서 가져오기 가능
                        if(x != 0)
                            g_areas[y][x].vec[num][cnt] += g_areas[y][x-1].vec[num][cnt];

                        g_areas[y][x].vec[num][cnt] %= DIV;
                    }
                    
                    // 오락실이 있는 경우
                    // 오락실 번호가 더 작은 경우에만 지나갈 수 있음
                    // 마지막은 제외
                    else if(idx != 0 && cnt != C && num < idx)
                    {
                        // 해당 오락실 번호로 모두 이동
                        // 위쪽에서 가져오기 가능
                        if(y != 0)
                            g_areas[y][x].vec[idx][cnt+1] += g_areas[y-1][x].vec[num][cnt];

                        // 왼쪽에서 가져오기 가능
                        if(x != 0)
                            g_areas[y][x].vec[idx][cnt+1] += g_areas[y][x-1].vec[num][cnt];

                        g_areas[y][x].vec[idx][cnt+1] %= DIV;
                    }
                }
            }
        }
    }
}

// 결과 출력
void printResult(const int N, const int M, const int C)
{
    vector<int> results(C+1, 0);
    for(int cnt = 0; cnt <= C; cnt++)
    {
        for(int num = 0; num <= C; num++)
        {
            results[cnt] += g_areas[N-1][M-1].vec[num][cnt];
            results[cnt] %= DIV; 
        }
    }

    for(const int& result : results)
        cout << result << " ";
    cout << "\n";
}

int main()
{
    // 입출력 최적화
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // 세로 N, 가로 M, 오락실 개수 C
    int N, M, C;
    cin >> N >> M >> C;

    inputInfo(N, M, C);
    simulate(N, M, C);
    printResult(N, M, C);
}

 

---

04. 마무리

경우나 크기 계산해 시간 & 공간 복잡도를 정확하게 알면, n차원 배열을 써도 문제가 없음을 깨달았습니다.

이전에는 3차원 이상의 문제에 대해 두려움이 있었지만, 이 문제를 해결하고 어느 정도 극복할 수 있었습니다.

 

---

 

읽어주셔서 감사합니다.

틀린 내용 지적은 언제나 환영입니다!