BOJ 거리

작성일 | In

[백준] 12026번 - BOJ 거리

문제 링크

이 문제의 조건은 두 가지이다.

  • 앞으로 전진할 때 B,O,J 영문자 순서대로 밟으며 전진해야 한다.
  • 마지막 인덱스에 도달할 수 있다면 최소값으로 도달해야 하고, 그럴 수 없다면 -1을 출력해야 한다.

처음에는 이 문제를 greedy 알고리즘을 통해 풀 수 있을거라 생각했다. 현재 블록이 B라면, 여기서 가장 가까운 O 블록을 밟는 방법으로 문제를 풀었지만 문제의 예제 입력6을 보고 잘못된 알고리즘임을 알았다.

greedy한 방법을 사용할 수 없다면, 완전탐색 알고리즘으로는 풀리지 않을까? 라는 생각에 접어들었다. n의 크기가 최대 1000이므로 가능성 있을 거라 생각했지만, 시간복잡도를 계산해보니 그렇지 않았다.
완전 탐색을 할 때 가장 경우의 수가 많아지는 경우는 주어지는 블록 상태가 BOJBOJBO….JBOJ 와 같이 BOJ문자열이 k개 연속되어 있는 형태이다. 이 때 가능한 모든 경우의 수를 어림잡아 보자면

  • i=0 위치의 B와 i=1위치의 O를 밟았을 때, 밟을 수 있는 J블록의 개수는 k개이다.
  • i=0 위치의 B와 i=4위치의 O를 밟았을 때, 밟을 수 있는 J블록의 개수는 k-1개이다.
  • i=0 위치의 B와 i=7위치의 O를 밟았을 때, 밟을 수 있는 J블록의 개수는 k-2개이다.

이와 같은 규칙으로 모든 경우의 수를 계산해보면 아래와 같은 식이 나온다.
$모든 경우의 수 = \Sigma_{i=1}^k (i *\Sigma_{z=1}^iz) = \Sigma_{i=1}^k \frac{i^2(i+1)}{2}$
이 식의 최고차항은 $k^4$ 이고, k는 최대 333.333…이므로 백억 이상의 결과가 나온다. 즉, 시간초과가 날 수밖에 없고, 실제로 구현해보니 시간초과가 났다.

고민 끝에 주어진 블록의 각 인덱스를 노드로 하고, 인덱스 간 차이의 제곱을 간선의 가중치로 하는 그래프를 만들고, 여기에 다익스트라 알고리즘을 적용하는 방법으로 구현했다. 다익스트라 알고리즘은 완전 탐색과는 달리 우선순위 큐를 이용하여 모든 경우의 수를 탐색하지 않는다. 시간복잡도도 $O(ElogE)$ 정도이고, 간선(E)의 개수는 계산해보니 최대 $\frac{3k^2}{2}$개 여서 시간제한에 걸리지 않을 것이라 예상했다. 구현 결과 문제 풀이에 성공했다.

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
#include <bits/stdc++.h>
using namespace std;

int n;
char str[1001];
vector<vector<pair<int, int>>> adj;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
int dst[1001];

void bfs() {
    pq.push({0, 0});

    while(!pq.empty()) {
        int cur = pq.top().second;
        int psum = pq.top().first;
        pq.pop();

        for(int i=0; i<adj[cur].size(); ++i) {
            int next = adj[cur][i].first;
            int cost = adj[cur][i].second;
            int nsum = psum + cost;
            if(nsum >= dst[next])
                continue;
            
            dst[next] = nsum;
            pq.push({nsum, next});
        }
    }
}

int main(void) {
    scanf("%d", &n);
    scanf("%s", str);

    adj.resize(n);
    for(int i=0; i<n; ++i) {
        char cur = str[i];
        char next;
        switch(cur) {
            case 'B': next = 'O'; break;
            case 'O': next = 'J'; break;
            case 'J': next = 'B'; break;
        }
        for(int j=i+1; j<n; ++j) {
            if(str[j] == next)
                adj[i].push_back({j, (j-i)*(j-i)});
        }

        dst[i] = INT_MAX;
    }
    dst[0] = 0;

    bfs();

    if(dst[n-1] == INT_MAX)
        printf("-1");
    else
        printf("%d", dst[n-1]);
}

문제를 풀고 알고리즘 분류를 살펴보니 동적 계획법이었다. 이에 다른 사람들의 풀이를 살펴보았고, 훨씬 간단하게 시간복잡도 $O(n^2)$로 풀어내는 방법이 있었다.
dp[i]를 i인덱스까지 도달하는데 소모되는 최소 에너지량이라고 생각하면, $dp[i] = dp[j] + (i-j)^2$ 라는 식을 세울 수 있다. (이 때 str[j]는 str[i]와 연쇄되는 문자여야 한다.)

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
#include <bits/stdc++.h>
using namespace std;
#define MAX 2100000000

int main(void) {
    int n;
    scanf("%d", &n);

    int arr[n];
    for(int i=0; i<n; ++i) {
        char temp;
        scanf(" %c", &temp);
        switch(temp) {
            case 'B': arr[i] = 0; break;
            case 'O': arr[i] = 1; break;
            case 'J': arr[i] = 2; break;
        }
    }

    int dp[n];
    for(int i=1; i<n; ++i)
        dp[i] = MAX;
    dp[0] = 0;

    for(int i=1; i<n; ++i) {
        for(int j=i-1; j>=0; --j) {
            int cost = (i-j) * (i-j);
            if(((arr[j] + 1) % 3 == arr[i]) && (dp[j] + cost < dp[i]))
                dp[i] = dp[j] + cost;
        }
    }

    printf("%d", dp[n-1] == MAX ? -1 : dp[n-1]);
}
0%