[백준] 2151번 거울 (C++)

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

 

 

이 문제는 N X N 격자가 주어지고 #(시작점, 도착점) 이 주어지는데

이때 시작점에서는 상하좌우 일직선으로 빛이 이동한다 이때 !지점에 거울을 설치할 수 있으며

거울에 도착한 경우 방향에 따라서 45도 회전하여 일직선으로 다시 이동한다.

 

이때 거울을 최소 배치하여 시작점에서 도착점까지 빛을 보내야하는 문제이다.

 

dp배열을 사용하여 위치 방향까지 기록하는 테이블을 기록하여 최댓값으로 갱신해주었으며

 

다익스트라 알고리즘을 사용하여 최소값을 출력하였다.

 

 

정답코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

struct coordinate {
    int x;
    int y;
    int r;
};

int dx[] = {-1, 1, 0, 0, 1, -1, -1, 1};
int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
int N;
char graph[51][51];
vector<pii> start;      // 0 시작 , 1 도착
int dist[51][51][4];
int cnt;

void Init() {
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            for(int k = 0; k < 4; k++) {
                dist[i][j][k] = MAX;
            }
        }
    }
}

int turn(int dir, char mirror) {
    if(mirror == '/') {
        if(dir == 0) return 3;
        if(dir == 1) return 2;
        if(dir == 2) return 1;
        else return 0;
    }
    else {
        if(dir == 0) return 2;
        if(dir == 1) return 3;
        if(dir == 2) return 0;
        else return 1;
    }
}

void dijkstra(int startx, int starty) {
    priority_queue<tuple<int, int, int, int>, vector<tuple<int, int, int, int>>, greater<tuple<int, int, int, int>>> pq;
    Init();
    for(int i = 0; i < 4; i++) {
        pq.push({0, i, startx, starty});
        dist[startx][starty][i] = 0;
    }

    while(!pq.empty()) {
        int x = get<2>(pq.top());
        int y = get<3>(pq.top());
        int cost = get<0>(pq.top());
        int dir = get<1>(pq.top());
        pq.pop();

        if(dist[x][y][dir] < cost) continue;

        int nx = x + dx[dir];
        int ny = y + dy[dir];

        if(nx < 0 || nx >= N || ny < 0 || ny >= N) continue;

        if(graph[nx][ny] == '*') continue;

        if(graph[nx][ny] == '.' || graph[nx][ny] == '#') {
            if(dist[nx][ny][dir] > cost) {
                pq.push({cost, dir, nx, ny});
                dist[nx][ny][dir] = cost;
            }
        }
        else if(graph[nx][ny] == '!') {
            int dirs = turn(dir, '/');

            if(dist[nx][ny][dir] > cost) {
                pq.push({cost, dir, nx, ny});
                dist[nx][ny][dir] = cost;
            }

            if(dist[nx][ny][dirs] > cost+1) {
                pq.push({cost+1, dirs, nx, ny});
                dist[nx][ny][dirs] = cost+1;
            }

            dirs = turn(dir, '\\');

            if(dist[nx][ny][dirs] > cost + 1) {
                pq.push({cost+1, dirs, nx, ny});
                dist[nx][ny][dirs] = cost + 1;
            }
        }
    }
}

void solve() {
    dijkstra(start[0].first, start[0].second);

    int answer = MAX;

    for(int i = 0; i < 4; i++) {
        answer = min(answer, dist[start[1].first][start[1].second][i]);
    }

    cout << answer;
}

void input() {
    cin >> N;

    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            cin >> graph[i][j];

            if(graph[i][j] == '#') {
                start.push_back({i, j});
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    input();
    solve();
}

 

먼저 dijkstra 함수를 살펴보면

void dijkstra(int startx, int starty) {
    priority_queue<tuple<int, int, int, int>, vector<tuple<int, int, int, int>>, greater<tuple<int, int, int, int>>> pq;
    Init();
    for(int i = 0; i < 4; i++) {
        pq.push({0, i, startx, starty});
        dist[startx][starty][i] = 0;
    }

    while(!pq.empty()) {
        int x = get<2>(pq.top());
        int y = get<3>(pq.top());
        int cost = get<0>(pq.top());
        int dir = get<1>(pq.top());
        pq.pop();

        if(dist[x][y][dir] < cost) continue;

        int nx = x + dx[dir];
        int ny = y + dy[dir];

        if(nx < 0 || nx >= N || ny < 0 || ny >= N) continue;

        if(graph[nx][ny] == '*') continue;

        if(graph[nx][ny] == '.' || graph[nx][ny] == '#') {
            if(dist[nx][ny][dir] > cost) {
                pq.push({cost, dir, nx, ny});
                dist[nx][ny][dir] = cost;
            }
        }
        else if(graph[nx][ny] == '!') {
            int dirs = turn(dir, '/');

            if(dist[nx][ny][dir] > cost) {
                pq.push({cost, dir, nx, ny});
                dist[nx][ny][dir] = cost;
            }

            if(dist[nx][ny][dirs] > cost+1) {
                pq.push({cost+1, dirs, nx, ny});
                dist[nx][ny][dirs] = cost+1;
            }

            dirs = turn(dir, '\\');

            if(dist[nx][ny][dirs] > cost + 1) {
                pq.push({cost+1, dirs, nx, ny});
                dist[nx][ny][dirs] = cost + 1;
            }
        }
    }
}

 

시작지점에서부터 우선순위 큐에 위치와 거울을 사용한 개수, 방향을 넣어주었으며

이전 방향에 따라서 계속 이동하였다.

 

이때 "!" 발견했을 경우 거울을 설치할 수 있는데 이때 거울을 놔서 방향을 바꾸는 경우

이전 방향과 똑같이 이동하는 경우가 있다. 두 경우를 모두 고려해서 구현하였으며

 

turn함수에서 거울을 놓아 방향을 바꾸는 로직을 작성하였다.

int turn(int dir, char mirror) {
    if(mirror == '/') {
        if(dir == 0) return 3;
        if(dir == 1) return 2;
        if(dir == 2) return 1;
        else return 0;
    }
    else {
        if(dir == 0) return 2;
        if(dir == 1) return 3;
        if(dir == 2) return 0;
        else return 1;
    }
}

 

거울은 /, \ 두 거울의 종류가 있으며 / 거울을 놓았을때 들어온 빛의 방향으로 45 회전한 방향을 반환해주었으며

마찬가지로 \ 거울도 45도 회전한 방향을 반환해주었다.