[TIL] 24.05.02 알고리즘

1. 알고리즘 문제 해결

 

 

변신 이동 게임(백준 15906):

 흔한 조건 몇 개 걸린 BFS 문제인 것 처럼 보였다. 결론부터 말하자면 그렇게 풀긴 했지만, 아마 A* 알고리즘을 적용했으면 더 널널하게 통과하지 않았을까싶다.

 

 격자의 최대 크기가 500*500으로 작았기 때문에 BFS로 접근했는데, 일단 당연하게도 방문 정보를 저장할 때는 단순하게 방문여부만 저장해서는 안된다. 일반 모드일 때와 변신 모드일 때로 나누어 저장해야 하고, 이전까지 있었던 방문 비용 최소치를 담아두기로 했다. 

 처음 작성했던 탐색과정은 이랬다.

 

- 큐의 front를 확인한다.

- 상태에 맞게 isVisited와 비교해서 값이 크거나 같다면 continue

- isVisited 갱신해 준 뒤에, 목적지에 도달했어도 continue

- 상하좌우 각각에 대해 일반모드로 한 칸씩 전진하는 경우가 유효한 지 검사한 후, 유효하다면 큐에 넣는다.(변신모드 해제는 걸리는 시간이 0이기 때문에, 시간 관련 변수는 현재값+1로 처리)

- 상하좌우 각 방향에 대해 한칸씩 쭉 전진하며 처음 워프 지점을 만나거나 끝에 도달할 때까지 진행한다. 이 때 처음 워프 지점을 만났다면 현재 모드에 따라 걸리는 시간을 계산하고 이를 큐에 넣는다.

- 큐가 빌 때까지 위 과정을 반복한다.

 

 유효한 지 검사할 때 당연히 isVisited랑 비교도 했는데, 저 변신모드로 각 방향의 워프 위치를 탐색하는 로직 때문에 시간 초과가 났다. 500*500짜리 그래프 상에서 두 유형으로 큐가 빌 때까지 완전하게 탐색한다고 해도 시간 초과가 나지는 않으므로 아마 저 로직의 문제가 맞을 것이다.

 이 때 몇 가지 고민을 했다. 먼저, 큐 대신 우선순위 큐를 이용해 다익스트라 알고리즘 처럼 풀까 생각했는데, 단순하게 소모된 시간이 적은 선택지를 우선적으로 탐색하는 방법은 목적지와 가까워진다는 보장이 없어서 조금 불안요소가 있다고 생각했다. 그렇다면 목적지와의 거리도 고려할 수 있도록, A* 알고리즘으로 구현할까 생각했는데 BFS를 최적화 하면 가능할 것 같아서 먼저 BFS 최적화부터 시도하기로 했다.

 

 n의 크기가 작기 때문에, 전처리를 통해서 미리 각 지점별로 상하좌우의 가장 가까운 워프 지점을 찾아둔다면, 반복되는 워프 지점 탐색 과정(O(2n)가량 소모되는데, 이게 BFS 과정에서 매번 발생하게 된다)을 O(1)로 줄여버릴 수 있다.

 그래서 격자 정보를 입력 받을 때, 각 워프 지점의 위치들을 바로 저장해뒀다가, 각각의 워프 지점들에 대해서 상하좌우 각 방향으로 끝까지 나아가며 나아간 지점에 대해 진입 방향을 구분해 그 거리를 갱신하도록 했다. 물론 끝에 도달하거나, 이미 같은 방향에서 더 짧은 거리의 워프 지점이 존재한다면 그 시점에서 해당 방향에 대한 갱신은 중단했다.

 이렇게 한다면 탐색이 최대 500*500*1,000번 가량, 그러니까 O(n^3)정도가 걸리는데, 시간 제한이 2초고 충분히 처리될 수 있었다. 그리고 사실 조금 생각해보면 알겠지만 저 최악의 경우는 절대 발생하지 않는다. 격자에 워프 지점으로 차있을 수록, 갱신과정에서 도중에 더 짧은 워프 지점이 있는 것을 확인할 가능성이 커지기 때문이다.

 

 저 방법으로 전처리를 통해 미리 warpDist 리스트를 정제해뒀고, 이를 BFS에 적용하자 바로 통과할 수 있었다. A* 알고리즘을 적용하거나 아니면 함께 적용했다면 이론적으로는 좀 더 빨랐을 것 같은데, n의 크기도 작고 케이스에 따라 달라질 거라, 실제 소모 시간을 따지자면 확신할 순 없을 것 같다.

 

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#define INF 987654321

using namespace std;

int dy[4] = {0, 1, 0, -1};
int dx[4] = {1, 0, -1, 0};

int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);

    int n, t, targetY, targetX;
    cin >> n >> t >> targetY >> targetX;
    targetY--;
    targetX--;

    vector<vector<vector<int> > > warpDist(n, vector<vector<int> >(n, {INF, INF, INF, INF})); //left, up, right, down
    vector<pair<int, int> >  warpPos;

    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            char c;
            cin >> c;
            if(c=='#') {
                warpPos.push_back({i, j});
            }
        }
    }

    for(auto pos: warpPos) {
        for(int i=0; i<4; i++) {
            int newY = pos.first;
            int newX = pos.second;
            int dist = 0;
            while(true) {
                newY += dy[i];
                newX += dx[i];
                dist++;

                if(!(newY>=0 && newY<n && newX>=0 && newX<n)) {
                    break;
                }else if(warpDist[newY][newX][i]>dist) {
                    warpDist[newY][newX][i] = dist;
                }else {
                    break;
                }
            }
        }
    }

    vector<vector<pair<int, int> > > isVisited = vector<vector<pair<int, int> > >(n, vector<pair<int, int> >(n, {INF, INF}));
    queue<pair<pair<int, int>, pair<int, int> > > q; //{{time, form}, {y, x}}
    q.push({{0, 0}, {0, 0}});

    while(!q.empty()) {
        int curTime = q.front().first.first;
        int curForm = q.front().first.second;
        pair<int, int> curPos = q.front().second;
        q.pop();

        if(curForm==0 && curTime>=isVisited[curPos.first][curPos.second].first) {
            continue;
        }else if(curForm==1 && curTime>=isVisited[curPos.first][curPos.second].second) {
            continue;
        }

        if(curForm==0) {
            isVisited[curPos.first][curPos.second].first = curTime;
        }else {
            isVisited[curPos.first][curPos.second].second = curTime;
        }

        if(curPos.first==targetY && curPos.second==targetX) {
            continue;
        }

        for(int i=0; i<4; i++) {
            int newY = curPos.first+dy[i];
            int newX = curPos.second+dx[i];

            if(newY>=0 && newY<n && newX>=0 && newX<n && isVisited[newY][newX].first>curTime+1) {
                q.push({{curTime+1, 0},{newY, newX}});
            }
        }

        for(int i=0; i<4; i++) {
            int newTime = curTime + (curForm==0?t+1:1);
            int newY = curPos.first;
            int newX = curPos.second;
            int dist = warpDist[curPos.first][curPos.second][i];
            if(dist==INF) continue;

            switch(i) {
                case 0: newX-=dist; break;
                case 1: newY-=dist; break;
                case 2: newX+=dist; break;
                case 3: newY+=dist; break;
            }

            if(isVisited[newY][newX].second>newTime) {
                q.push({{newTime, 1}, {newY, newX}});
            }   
        }
    }

    cout << min(isVisited[targetY][targetX].first, isVisited[targetY][targetX].second);
}