[TIL] 24.03.28 알고리즘, CS 리마인드

1. 알고리즘 문제 해결

 

알고스팟(백준 1261):

 어제 맥락이 같다고 했던 유형의 문제가 바로 나왔다. 결과적으로는 다익스트라 문제긴한데, 사실 BFS(Best-First Search, 이하 BFS) 문제라고 봐도 무방하다. Best의 판단 기준은 당연히 진행하면서 부순 벽의 수이다.

 문제의 입력으로 인접 노드가 아닌 미로의 평면 정보가 주어지고, 그 수 또한 많지 않으므로(최대 100*100개의 데이터가 주어지며 심지어 데이터는 0또는 1이다) 인접 정보는 2차원 배열에 그대로 저장한다. 이렇게 하면 각종 DFS, BFS( Breadth-First Search) 문제를 풀 때 자주 사용하던 방식으로 dx와 dy배열을 만들어 좀 더 간결한 코드를 작성할 수 있다.

 

 BFS를 사용하기로 했으므로 우선순위 큐를 이용할 것이고, 담기는 자료구조에는 현재 탐색 중인 좌표 정보 및 부순 벽에 관한 정보가 포함되어야 한다. 이번에는 따로 비교를 위한 구조체를 만들지 않고, 부순 벽의 수를 pair의 첫번째 인자로 넣고 음수를 취해 부순 벽의 수가 적을수록 높은 우선순위를 가지도록 했다.

 

 이후에는 우선순위 큐의 top을 뽑아 이미 더 나은 방법으로 탐색한 전적이 있는지 확인하고, 없다면 상하좌우의 좌표들을 확인해 벽 여부에 맞춰 비교해준다. 당연히 해당 좌표를 탐색할 때 벽을 부수는 횟수가 기존에 탐색할 때 있었던 최선치보다 더 적어야만 의미가 있다.

 이 과정을 반복하며 목표지점 좌표가 우선순위 큐의 top으로 뽑혀나오면 그 때 부순 벽의 수를 출력하고 루프를 종료한다.

 

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

using namespace std;

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

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

    int n, m;
    cin >> n >> m;

    vector<vector<bool> > maze(m, vector<bool> (n, false));
    vector<vector<int> > visited(m, vector<int> (n, INF));
    char c;

    for(int i=0; i<m; i++) {
        for(int j=0; j<n; j++) {
            cin >> c;
            maze[i][j] = c-'0';
        }
    }

    priority_queue<pair<int, pair<int, int> > > pq;
    pq.push({0, {0, 0}});
    visited[0][0] = 0;

    while(!pq.empty()) {
        int breakWall = pq.top().first;
        int curY = pq.top().second.first;
        int curX = pq.top().second.second;
        pq.pop();

        if(breakWall<visited[curY][curX]) continue;
        if(curY==m-1 && curX==n-1) {
            cout << -breakWall;
            break;
        }
        
        for(int i=0; i<4; i++) {
            int newX = curX+dx[i];
            int newY = curY+dy[i];
            if(newX>=0&&newX<n&&newY>=0&&newY<m) {
                if(maze[newY][newX]&&visited[newY][newX]<breakWall-1) {
                    visited[newY][newX] = breakWall-1;
                    pq.push({breakWall-1, {newY, newX}});
                }else if(!maze[newY][newX]&&visited[newY][newX]<breakWall) {
                    visited[newY][newX] = breakWall;
                    pq.push({breakWall, {newY, newX}});
                }
            }
        }
    }
}

 

 

2. CS 리마인드

 

 

 적지 않은 분량이라 며칠에 나누어 작성하고 있는데, 확실히 글로 다 정리하려니 진도가 잘 안나가긴 한다. 생각해보면 이미 시험기간 때 한번 쯤 다 타이핑해서 정리했던 것들인데, 예전 노트북을 뒤져보면 남아있을 것 같기도 하고..

 

 알고리즘 문제 풀이만 적고 올릴려니 뭔가 한 게 없어 보이는 느낌이라 이거라도 남긴다. 본 과제 제출을 위해서 부랴부랴 README도 작성하고 하느라 시간을 많이 써서, 글로 남길거리가 많지 않은 하루다.