알고리즘 - 1249. [S/W 문제해결 응용] 보급로 문제

SW Expert Academy 의 1249번 - 보급로 문제입니다.

본 풀이보다 더 간단한 DP 표현으로 작성할 수 있는 방법이 있습니다. 추후에 재 포스팅할 예정입니다.

• 난이도 : 3

문제 조건

n*n 의 2차원 배열이 주어지는데, 각 칸에 쓰여진 값은 그 칸을 복구하는 데 걸리는 시간입니다.

맨 왼쪽 위에서 출발하여 맨 오른쪽 아래로 도착하는 경로들 중에서 복구하면서 오는 데 걸리는 시간이 가장 짧은 경로를 찾는 문제입니다.

Input

• 한 개의 테스트 케이스 당
  • 지도의 크기 N과,
  • N x N에 해당하는 2차원 배열 데이터가 주어집니다.

Output

복구 작업에 드는 시간이 가장 적게 드는 경로의 복구 시간을 출력합니다.

생각한 아이디어

출발지에서 끝까지 갈 수 있는 모든 경우의 수를 살펴보는 것은 너무나 많아 보였습니다.

그래서 바로 생각이 나지 않았는데, 이렇게 길을 찾는 문제는 BFS를 많이 활용함을 알게 되었습니다.

왼쪽은 원래 데이터가 들어 있는 배열이고, 오른쪽은 특정 칸까지 이동하는 데 소요된 최소 복구 시간을 기록하기 위한 배열입니다. (INF는 임의의 매우 큰 수라고 가정합니다)

왼쪽 배열은 arr, 오른쪽 배열은 depArr 이라고 부르겠습니다.

• 먼저, 출발 지점의 좌표 (0, 0)을 큐에 push 합니다.
• 큐의 맨 앞의 데이터의 좌표를 읽어 변수에 저장해 놓은 뒤, pop 합니다.

• 위와 같이 현재 읽은 위치(idx_x, idx_y)에서 상, 하, 좌, 우로 갈 수 있는 곳을 찾습니다. 여기서는 우측과 하단으로 내려갈 수 있는데, 우측(0, 1) 먼저 확인합니다.

  • next_x = 0, next_y = 1인 위치에 대해서

    1 2	depArr[next_x][next_y] > depArr[idx_x][idx_y] + arr[next_x][next_y] // 즉, depArr[0][1] > depArr[0][0] + arr[0][1]

    이면, 다음 좌표인 (0, 1) 로 가는 더 짧은 경로를 발견한 것이 됩니다. 그러므로,

    1 2	depArr[next_x][next_y] = depArr[idx_x][idx_y] + arr[next_x][next_y] // 즉, depArr[0][1] = depArr[0][0] + arr[0][1];

    로 대입을 합니다.

• 위 그림처럼 depArr (0, 1) 위치에 새로이 값이 대입되었고, (0, 1)을 큐에 push합니다.

• 이제 하단인 (1, 0) 위치를 봅니다.

  • next_x = 1, next_y = 0인 위치에 대해서

    1 2	depArr[next_x][next_y] > depArr[idx_x][idx_y] + arr[next_x][next_y] // 즉, depArr[1][0] > depArr[0][0] + arr[1][0]

    이면, 다음 좌표인 (0, 1) 로 가는 더 짧은 경로를 발견한 것이 됩니다. 그러므로,

    1 2	depArr[next_x][next_y] = depArr[idx_x][idx_y] + arr[next_x][next_y] // 즉, depArr[1][0] = depArrr[0][0] + arr[1][0];

    로 대입을 합니다.

• 위 그림처럼 depArr (1, 0) 위치에 값이 새로 대입되었고, (1, 0)을 큐에 push합니다.

• 이제 큐의 맨 앞의 데이터를 꺼내어 그 좌표로 이동합니다.

• (0, 1) 위치에서는 좌, 우, 하단을 갈 수 있습니다.
• 이 때 하단인 (1,1)을 확인합니다.

• next_x = 1, next_y = 1인 위치에 대해서

1
2

  depArr[next_x][next_y] > depArr[idx_x][idx_y] + arr[next_x][next_y] 
  // 즉, depArr[1][1] > depArr[0][1] + arr[1][1]

이면, 다음 좌표인 (0, 1) 로 가는 더 짧은 경로를 발견한 것이 됩니다. 그러므로,

1
2

  depArr[next_x][next_y] = depArr[idx_x][idx_y] + arr[next_x][next_y]
  // 즉, depArr[1][1] = depArrr[0][1] + arr[1][1];

로 대입을 합니다.

• 위 그림처럼 depArr (1, 1) 위치에 값이 새로 대입되었고, (1, 1)을 큐에 push합니다.
• 이제 오른쪽 좌표 (0, 2)를 확인합니다.

• 같은 방식으로 depArr 을 업데이트 한 뒤, (0, 2)를 큐에 push합니다.

위와 같은 방식으로 진행을 계속하여, 큐가 empty 상태가 될 때까지 반복합니다.

정리하자면 다음과 같습니다.

• 현재 칸 (idx_x, idx_y) 기준으로 갈 수있는, 다음 칸인 상, 하, 좌, 우를 검사합니다.
  • 맨 처음에는 (0, 0)부터 시작합니다.
• 다음 칸의 depArr 값이, 현재 칸의 depArr 값 + 다음 칸의 arr 값보다 크면
  • 다음 칸의 depArr 값을 현재 칸의 depArr 값 + 다음 칸의 arr 값 으로 갱신 후 다음 칸의 좌표를 큐에 push
  • 그렇지 않다면 갱신 및 푸쉬하지 않고 다른 다음 칸으로 넘어감
• 이것을 큐가 빌 때까지 반복하면 됩니다.
• 최종적으로 depArr의 맨 오른쪽 맨 아래 칸에 적힌 값이 최소 복구 시간이 될 것입니다.

쉽게 말해 depArr 에 있는 값은, 해당 칸까지 오는 데 소모된 복구 시간을 기록하기 위한 목적입니다.

다음 칸에 가기까지 소모된 복구 시간(depArr의 next에 있는 값)이, 현재 칸에 오기까지 소모된 복구 시간(depArr의 현재 idx에 있는 값) 과 현재 칸의 복구시간의 합보다 작다면, 다음 칸에 가기까지 더 작은 복구 시간을 가지게 된 것이므로 이것으로 값을 갱신한 것입니다.

그리고 이 방법이 BFS인 이유는, 현재 칸을 기준으로 인접한 상, 하, 좌, 우 칸을 차례로 확인하고 큐에 push하기 때문입니다.

소스코드

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

#define INF 999999
#include <cstdio>
#include <cstdlib>
#include <queue>
using namespace std;

int arr[101][101];
int depArr[101][101];

// 상, 하, 좌, 우
int dx[4] = { 0,0,-1,1 };
int dy[4] = { -1,1,0,0 };

int main() {

    int test_case, N, idx_x, idx_y;
    int path;
    queue<pair<int, int>> q;

    scanf("%d", &test_case);
    for (int T = 1; T <= 10; T++) {
        scanf("%d", &N);

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                scanf("%1d", &arr[i][j]);
                depArr[i][j] = INF;
            }
        }
        depArr[0][0] = 0;
        // 여기까지 하면 자료 입력받기 완료
        // 맨 처음 칸에 대한 계산을 위해, dep

        q.push(make_pair(0, 0));

        while (q.size()) {
            idx_x = q.front().first;
            idx_y = q.front().second;
            q.pop();

            /* 상, 하, 좌, 우 좌표를 큐에 넣기 */
            for (int i = 0; i < 4; i++) {
                int next_x = idx_x + dx[i];
                int next_y = idx_y + dy[i];

                if (next_x < 0 || next_x >= N || next_y < 0 || next_y >= N)
                    continue;

                // 경로의 합 (다음에 갈 곳의 값이 
                if (depArr[next_x][next_y] > depArr[idx_x][idx_y] + arr[next_x][next_y]) {
                    depArr[next_x][next_y] = depArr[idx_x][idx_y] + arr[next_x][next_y];
                    q.push(make_pair(next_x, next_y));
                }
            }
        }
        // 최종적으로 맨 마지막 칸에 있는 값을 출력하면 답이 된다.
        printf("#%d %d\n", T, depArr[N - 1][N - 1]);
    }

}