[신촌 ICPC 알고리즘 캠프] 최단거리 알고리즘 (24.01.22)

해당 수업에서 최단거리를 구하는 여러 가지 알고리즘에 대해 간단히 리뷰했다. 0-1 BFS, 다익스트라, 벨만포드 정도를 간단하게 알려주셨다. 직접 해당하는 알고리즘의 문제를 풀면서 배운 점을 적어놓으려고 한다.

 

13549 - 숨바꼭질 3 (G5)

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

이 문제는 아마도 저번 여름 캠프때 나왔던 것 같다. 이미 풀려있는 문제여서 다시 C++으로 풀어보면서 재제출했다.

사실 내게 다익스트라는 골드 하위 문제 날먹 알고리즘 정도였는데.. 한 때 스트릭 용으로 G4~G5 정도의 기본 다익 문제만 푼 적이 있다. 그런데 이렇게 연습해도 응용 문제가 되면 헷갈리는 것 같다. 아직 경험이 부족해서 그런가보다. 그래프의 형태가 기본 그래프와 달라지거나, 특수한 이동 조건이 붙었을 때의 다익스트라 적용을 잘하고 싶다. 그래서 이번 주 캠프 문제들을 풀면서 특수 조건이 있는 그래프 문제를 시도해봐야겠다고 생각했다.

 

2423 - 전구를 켜라 (G1)

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

이 문제는 '다익스트라' or '0-1 BFS' 응용으로 풀 수 있다. 내가 처음에 떠올린 방법은 각 grid의 꼭짓점을 node라고 생각하고, 경로가 연결되어 있다면 그대로 진행, 아니면 경로를 90도 돌리고 cnt++ 해준 후 이동 노드를 cnt와 함께 우선순위 큐에 넣어 cnt를 최소화 하게끔 다익스트라를 돌리는 것이었다.

이대로 구현을 진행하는데 경로 상태 그래프를 어떻게 표현할지 고민을 했다. 처음에는 각 노드를 연결할 때 직접적으로 어느 노드와 연결되어있는지 일일히 좌표 값을 인접 리스트에 넣어주었는데, 이는 경로를 90도로 회전했을 때 바뀐 경로로 인접 리스트를 수정해야 하는 일이 필연적으로 발생하고... 기존 목적지 노드를 삭제하고 새로운 곳을 추가하고~~ 이런식으로 가다보면 필연적으로 안될거라고 생각했다. 그래서 여러 방법을 시도하다가 애초에 모든 칸에 X자 경로를 그어버리면 안되나? 싶었다. 기존 경로를 타고 이동하면 회전 cnt를 더하지 않고, 경로를 90도 돌려야 하면 cnt += 1 해주면 될 것 같았다.

이렇게 경로 설정만 해주고 그대로 다익스트라를 돌려봤다. 그런데 자꾸 인덱스 오류가 나서 다시 봤는데 dist와 grid는 열, 행 순서인데 좌표는 x축, y축으로 해줘서 서로 반대가 되어야하고 이걸 코드 중에 한 군데 실수해서 자꾸 오류가 나는거였다... 다시 고쳐준 후에 AC를 받았다.

아무래도 그래프를 다루는 문제는 python이 손에 익는다. 이번 캠프 때 C++ 으로 풀려고 했는데 역시 파이썬으로 먼저 풀고 그 다음에 코드를 옮기면서 손에 익도록 연습을 하는게 나을 것 같다.

import sys
input = sys.stdin.readline
n, m = map(int, input().split())
grid = [[[] for _ in range(m+1)] for _ in range(n+1)]

for i in range(n):
    line = input().rstrip()
    for j in range(m):
        if line[j] == '/': # cnt, x, y 순서, 90도 돌려야 하면 cnt+=1
            grid[i][j+1].append((0, j, i+1))
            grid[i+1][j].append((0, j+1, i))
            grid[i][j].append((1, j+1, i+1))
            grid[i+1][j+1].append((1, j, i))
        else:
            grid[i][j].append((0, j+1, i+1))
            grid[i+1][j+1].append((0, j, i))
            grid[i][j+1].append((1, j, i+1))
            grid[i+1][j].append((1, j+1, i))

import heapq as hq
INF = sys.maxsize

def dijkstra(x, y):
    dist = [[INF] * (m+1) for _ in range(n+1)]
    PQ = [(0, x, y)]
    dist[y][x] = 0

    while PQ:
        cnt, x, y = hq.heappop(PQ)
        if dist[y][x] < cnt:
            continue

        for ncnt, nx, ny in grid[y][x]:
            tmp = cnt + ncnt
            if dist[ny][nx] > tmp:
                dist[ny][nx] = tmp
                hq.heappush(PQ, (tmp, nx, ny))
    #print(dist)
    return dist[n][m]

res = dijkstra(0, 0)
print(res if res < INF else "NO SOLUTION")

 

C++으로 다익스트라를 구현할 때면 우선순위 큐 선언이 너무 길다는 생각이 든다. 너무 간략한거에만 익숙해져서 그런가... 특히 다른 사람 코드 보면서 공부할 때 파이썬 위주로 봐서 어떤 구현이 예쁜 구현인지..? 구조체 선언 같은 부분이나.. 포인터, STL 도 추가로 공부를 해야할 것 같다.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int n, m;
const int INF = 1e9;
vector<vector<vector<pair<int, pair<int, int>>>>> grid;

int dijkstra(int x, int y){
    vector<vector<int>> dist(n+1, vector<int>(m+1, INF));
    priority_queue<pair<int, pair<int, int>>> PQ;

    dist[y][x] = 0;
    PQ.push({0, {x, y}});

    while (!PQ.empty()) {
        int cnt = -PQ.top().first;
        int x = PQ.top().second.first;
        int y = PQ.top().second.second;
        PQ.pop();

        if (dist[y][x] < cnt) continue;

        for (const auto &edge : grid[y][x]) {
            int nx = edge.second.first;
            int ny = edge.second.second;
            int new_dist = cnt + edge.first;

            if (dist[ny][nx] > new_dist) {
                dist[ny][nx] = new_dist;
                PQ.push({-new_dist, {nx, ny}});
            }
        }
    }
    int ret = dist[n][m];
    return ret;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> m;
    grid.resize(n+1, vector<vector<pair<int, pair<int, int>>>>(m+1));

    for (int i=0; i < n; i++){
        string line;
        cin >> line;
        for (int j=0; j < m; j++){
            if (line[j] == '/') { //여기도 x, y 순서 조심
                grid[i][j+1].push_back({0, {j, i+1}});
                grid[i+1][j].push_back({0, {j+1, i}});
                grid[i][j].push_back({1, {j+1, i+1}});
                grid[i+1][j+1].push_back({1, {j, i}});
            } else {
                grid[i][j].push_back({0, {j+1, i+1}});
                grid[i+1][j+1].push_back({0, {j, i}});
                grid[i][j+1].push_back({1, {j, i+1}});
                grid[i+1][j].push_back({1, {j+1, i}});
            }
        }
    }
    int ret = dijkstra(0, 0);
    if (ret < INF) {
        cout << ret;
    } else {
        cout << "NO SOLUTION";
    }
    return 0;
}

 

공부를 하다가 이 문제를 0-1 BFS로는 어떻게 풀지 궁금해서 찾아보았다.

https://rapun7el.tistory.com/231

[백준 2423번] 전구를 켜라 (Python3)

글을 읽으면서 이런 방법도 있었구나 하고 신기했다. 특히 거리 순으로 deque 앞에 넣을지 뒤에 넣을지 해주면서 판단한게 새로운 방법인 것 같았다. 0/1 로 상태를 두가지로 표현한 것도 새로웠다. 나는 그래프 문제를 거의 다 노드로 접근하려고 하고, 노드를 어떻게 표현할지를 생각하느라 생각이 굳는 경향이 있는데 다음에 이 방법으로도 구현해봐야겠다.