문제

나의 요약

미로가 주어지고, 미로의 칸에 있는 화살표대로 움직여야 한다.
미로를 탈출하지 못하는 경우에는 칸에 점프대를 설치해 바로 빠져나오게 한다.
점프대 설치에는 Cost(i,j) 만큼의 비용이 든다. 최소한의 비용으로 어느 칸에서 시작해도 미로를 탈출하게 하자.

접근 방법

미로를 DFS로 모든 정점을 순회하고, 이미 방문한 정점을 만나면 사이클이라는 뜻이니 사이클 안의 최소 비용을 찾아 답에 더해주자.

DFS를 하며 한번 지나간 정점들에 대해서는 다시 DFS를 진행할 필요가 없으니 무시하고, 나머지 정점들에 대해서만 DFS를 진행하면 된다.

풀이

#include <bits/stdc++.h>
using namespace std;

int N, M;
int ans;
vector<string> maze;
vector<vector<int>> cost;
vector<vector<bool>> visited;
vector<vector<bool>> canEscape;
unordered_map<char, int> m;

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

void Input()
{
    cin >> N >> M;
    maze.resize(N);
    for (int i = 0; i < N; i++)
    {
        cin >> maze[i];
    }

    cost.resize(N, vector<int>(M));
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cin >> cost[i][j];
        }
    }
}

bool IsInMaze(int x, int y)
{
    return x >= 0 && x < N && y >= 0 && y < M;
}

void DFS(int x, int y)
{
    int nx, ny;
    if (visited[x][y])
    {
        if (!canEscape[x][y])
        {
            nx = x;
            ny = y;

            int minCost = cost[nx][ny];
            do
            {
                int dir = m[maze[nx][ny]];              
                nx += dx[dir];
                ny += dy[dir];

                if (cost[nx][ny] < minCost) minCost = cost[nx][ny];
            } while (!(nx == x && ny == y));

            ans += minCost;
        }
        return;
    }

    visited[x][y] = true;
    nx = x + dx[m[maze[x][y]]];
    ny = y + dy[m[maze[x][y]]];

    if (IsInMaze(nx, ny)) DFS(nx, ny);
    canEscape[x][y] = true;
}

void Solve()
{
    ans = 0;
    canEscape.assign(N, vector<bool>(M, false));
    visited.assign(N, vector<bool>(M, false));

    m['U'] = 0;
    m['D'] = 1;
    m['L'] = 2;
    m['R'] = 3;

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            if (!canEscape[i][j]) DFS(i, j);
        }
    }

    cout << ans;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    Input();
    Solve();
}

재귀 방식으로 DFS를 진행한다. 이미 방문 중이지만, 끝까지 완료되지는 않은 정점이 있다면, 새 사이클을 찾았다는 뜻이니 사이클을 다시 순회해보며 가장 작은 비용을 찾아서 답에 더해준다.

만약 방문 중인데 끝까지 완료된 정점을 탐색한다면, 지금의 DFS가 아닌 전의 DFS에서 탐색이 완료된 정점이니 굳이 비용에 대한 탐색을 하지 않는다.

화살표를 가리키는 다음 정점이 미로 밖이라면, 탈출을 했다는 뜻이니 탐색을 더 진행하지 않는다.

회고

크게 놓친 점이 '방문 중인데 끝까지 완료하지는 않은 정점'을 만났을 때 사이클로 취급하는 것이었다. 사실 끝까지 완료하지 했다면 이미 전의 DFS에서 탐색이 완료된 정점이기 때문에 다시 탐색할 필요가 없는 것이다.
탐색이 완료가 되었다는 것을 따로 저장해두어야 하기 때문에, 재귀 방식으로 푸는 것이 구현에 쉬웠다.

2시간 반이나 걸렸다. 사실상 틀렸다고 봐도 무방... 풀이가 1시간을 넘어가고 나니 집중력이 급격히 떨어져 이상한 인덱스 실수도 너무 자주 나와 풀이가 배로 걸렸다... 한 번 풀이가 어긋나서 다시 어떻게 접근해야하는지 멘탈이 나갈 때가 있는데, 잘 잡고 문제를 처음부터 본다는 생각으로 해보자.