[백준] 30689 - 미로 보수

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

 

알고리즘

그래프 이론 / 그래프 탐색 / 깊이 우선 탐색 / 함수형 그래프

설명

이전에 풀었던 텀 프로젝트 문제와 비슷한 느낌이 난다.

재귀를 통하여 구현

해당 유형은 익숙하지가 않아 구현 실수가 많은 것 같다.

이번 차례에 방문한 칸과 이전에 방문했던 칸을 체크하는 두 개의 vistied 배열을 사용하여 미로 내의 사이클을 찾는 문제

만약 사이클을 발견하게 되면, 사이클을 이루는 칸 중 가장 비용이 작은 칸을 정답에 더해준다.

코드

#include <iostream>
#include <queue>
#include <vector>
#include <cmath>
#include <map>
#include <stack>
#include <unordered_map>
#include <cstring>
#include <algorithm>
using namespace std;
int N, M;
string arr[2000];
struct yx {
    int y, x;
};
int visited[2000][2000];
int done[2000][2000];
int cost[2000][2000];
int dy[4] = { 1, -1, 0, 0 };
int dx[4] = { 0, 0 ,1 , -1 };
int answer = 0;
unordered_map<char, int> m;
void dfs(int py, int px)
{
    //cout << py << " " << px << '\n';
    visited[py][px] = 1;
    int dir = m[arr[py][px]];
    int y = dy[dir] + py;
    int x = dx[dir] + px;
    if (x < 0 || y < 0 || x >= M || y >= N) {
        //out
        done[py][px] = 1;
        return;
    }
    if (done[y][x]) {
        done[py][px] = 1;
        return;
    }
    else if (visited[y][x]) {
        int sy = y;
        int sx = x;
        int cc = 987654321;
        do
        {
            cc = min(cc, cost[sy][sx]);
            int d = m[arr[sy][sx]];
            sy = dy[d] + sy;
            sx = dx[d] + sx;
        } while (sy != y || sx != x);
        answer += cc;
    }
    else dfs(y, x);
    done[py][px] = 1;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    m['U'] = 1;
    m['D'] = 0;
    m['L'] = 3;
    m['R'] = 2;
    cin >> N >> M;
    for (int i = 0; i < N; ++i) {
        cin >> arr[i];
    }
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            cin >> cost[i][j];
        }
    }
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            if (done[i][j]) continue;
            dfs(i, j);
        }
    }
    cout << answer;
    return 0;
}