레이저 통신 6087

23.6.14 수정 (재채점)

문제

접근 방법

거울을 놓는다는 건 방향을 바꾼다는 것이다.
이전의 방향을 저장해 두고 방향이 바뀔 때마다 1씩 증가해 준다고 생각하면 된다. 이미 지나간 곳일지라도 방향이 다르면 다른 값이 나오거나 다른 좌표에 필요한 디딤돌이 될 수 있으니 무시해선 안 된다고 생각했다.

23.06.14 추가

하지만 같은 값으로 같은 위치에 도달한 경우에는 같은 방향으로 가는지 확인해 볼 필요가 있다. 가운데에 점하나를 두고 왼쪽에서 오른쪽으로 간다면 위, 아래 2방향으로 같은 값, 같은 방향으로 도착한다.

거울	->	거울
시작	벽	겹침
거울	->	거울

그렇기에 해당 위치에서의 방향에 대한 중복 방문 처리를 해줘야 한다.

이전 코드

#include <iostream>
#include <queue>
#include <climits>
#include <vector>
using namespace std;
struct node
{
    int y, x, dy, dx, mirror;
};
int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int W, H;
    pair<int, int> start, end;
    cin >> W >> H;
    vector<vector<int>> map(H, vector<int>(W, INT_MAX));
    queue<node> bfs;
    bool init = false;
    for (int i = 0; i < H; ++i)
    {
        for (int j = 0; j < W; ++j)
        {
            char c;
            cin >> c;
            if (c == '.')
                map[i][j] = INT_MAX;
            else if (c == '*')
                map[i][j] = -1;
            else
            {
                if (init)
                {
                    end = {i, j};
                    map[i][j] = INT_MAX;
                }
                else
                {
                    init = true;
                    start = {i, j};
                    map[i][j] = -1;
                }
            }
        }
    }
    bfs.push({start.first, start.second, 0, 0, -1});
    while (!bfs.empty())
    {
        node cur = bfs.front();
        bfs.pop();
        for (int i = 0; i < 4; ++i)
        {
            int weight = ((cur.dy == dy[i] && cur.dx == dx[i]) ? 0 : 1);
            node next = {cur.y + dy[i], cur.x + dx[i], dy[i], dx[i], cur.mirror + weight};
            if (next.y < 0 || next.x < 0 || next.y >= H || next.x >= W)
                continue;
            if (next.mirror > map[next.y][next.x])
                continue;
            map[next.y][next.x] = next.mirror;
            bfs.push(next);
        }
    }
    cout << map[end.first][end.second];
    return 0;
}

수정 코드

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

typedef pair<int, int> pii;
typedef pair<pii, pii> ppp; // 거울 개수, 방향, 위치
int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
int main()
{
    ios_base::sync_with_stdio(0), cin.tie(0);
    int W, H;
    cin >> W >> H;
    vector<vector<int>> map(H, vector<int>(W, INT_MAX));
    vector<vector<vector<bool>>> isVisted(H, vector<vector<bool>>(W, vector<bool>(4)));
    priority_queue<ppp, vector<ppp>, greater<ppp>> pq;
    pii end;
    for (int i = 0; i < H; ++i)
        for (int j = 0; j < W; ++j)
        {
            char c;
            cin >> c;
            if (c == '*')
                map[i][j] = -1;
            else if (c == 'C')
            {
                if (pq.empty())
                {
                    pq.push({{0, -1}, {i, j}});
                    map[i][j] = 0;
                    isVisted[i][j][0] = isVisted[i][j][1] = isVisted[i][j][2] = isVisted[i][j][3] = true;
                }
                else
                    end = {i, j};
            }
        }
    while (!pq.empty())
    {
        ppp cur = pq.top();
        pq.pop();
        int y = cur.second.first, x = cur.second.second, mirror = cur.first.first;
        if (map[y][x] < mirror)
            continue;
        for (int dir = 0; dir < 4; ++dir)
        {
            int weight = cur.first.second == dir ? 0 : 1, nextMirror = mirror + weight;
            int ny = y + dy[dir], nx = x + dx[dir];

            ppp next = {{nextMirror, dir}, {ny, nx}};
            if (ny < 0 || nx < 0 || ny >= H || nx >= W || map[ny][nx] < nextMirror || (isVisted[ny][nx][dir] && map[ny][nx] == nextMirror))
                continue;
            isVisted[ny][nx][dir] = true;
            map[ny][nx] = nextMirror;
            if (ny == end.first && nx == end.second)
                break;
            pq.push(next);
        }
    }
    cout << map[end.first][end.second] - 1;
    return 0;
}

풀이

이 문제에서 가장 먼저 도착지에 도착하더라도 최소 거울이 아닐 수 있다. 그렇기에 목적지에 도달해도 break 하지 않는 것이 좋다. (더 멀리서 돌아오더라도 최소 거울일 수 있기에 그렇다)
또한 이차원 벡터에서 값을 가져와서 갱신해주는 것을 해서는 안 된다. 큐에 집어넣고 기다리다가 내 차례가 됐을 때 이차원 벡터에 저장된 값이 이미 다른 레이저에 의해 수정됐을 수도 있기 때문이다. 그렇기에 큐에 같이 저장해주는 것이 좋다. (map[next.y][next.x] = map[cur.y][cur.x]+weight 이런 식으로 작성하면 안 된다는 뜻이다)

23.06.14 추가 및 수정

BFS에서 다익스트라로 수정하였다. 물론 BFS로도 풀 수 있을 것 같다.
BFS에서는 가장 먼저 도착지에 도착하더라도 최소 거울이 아니다. 하지만 다익스트라를 활용한다면 가장 먼저 도착하는 것이 최소 거울이다.

만약 우선순위 큐에 들어있는 값이 현재 위치에 저장된 값보다 크다면 고려해 볼 필요 없는 값이다.

만약 다음 위치에 값과 현재 위치의 값이 같다면 이미 해당 방향으로 진행했는지 확인하면 된다.