[백준 c++] 2151 거울 설치

문제

채영이는 거울을 들여다보는 것을 참 좋아한다. 그래서 집 곳곳에 거울을 설치해두고 집 안을 돌아다닐 때마다 거울을 보곤 한다.

채영이는 새 해를 맞이하여 이사를 하게 되었는데, 거울을 좋아하는 그녀의 성격 때문에 새 집에도 거울을 매달만한 위치가 여러 곳 있다. 또한 채영이네 새 집에는 문이 두 개 있는데, 채영이는 거울을 잘 설치하여 장난을 치고 싶어졌다. 즉, 한 쪽 문에서 다른 쪽 문을 볼 수 있도록 거울을 설치하고 싶어졌다.

채영이네 집에 대한 정보가 주어졌을 때, 한 쪽 문에서 다른 쪽 문을 볼 수 있도록 하기 위해 설치해야 하는 거울의 최소 개수를 구하는 프로그램을 작성하시오.

거울을 설치할 때에는 45도 기울어진 대각선 방향으로 설치해야 한다. 또한 모든 거울은 양면 거울이기 때문에 양 쪽 모두에서 반사가 일어날 수 있다. 채영이는 거울을 매우 많이 가지고 있어서 거울이 부족한 경우는 없다고 하자.

거울을 어떻게 설치해도 한 쪽 문에서 다른 쪽 문을 볼 수 없는 경우는 주어지지 않는다.

입력
첫째 줄에 집의 크기 N (2 ≤ N ≤ 50)이 주어진다. 다음 N개의 줄에는 N개의 문자로 집에 대한 정보가 주어진다. ‘#’는 문이 설치된 곳으로 항상 두 곳이며, ‘.’은 아무 것도 없는 것으로 빛은 이 곳을 통과한다. ‘!’은 거울을 설치할 수 있는 위치를 나타내고, ‘*’은 빛이 통과할 수 없는 벽을 나타낸다.

출력
첫째 줄에 설치해야 할 거울의 최소 개수를 출력한다.

풀이

1. checked[51][51][4]: y,x,방향을 저장하고 방문체크
   방문체크는 거울 사용개수를 기준으로 한다.
   먼저 방문했다고해서 거울을 적게 사용한 것이 아니 때문

if (checked[ny][nx][d] > cnt){
	q.push({{ny, nx}, {d, cnt}});
	checked[ny][nx][d] = cnt;
}
//다음 진행할 좌표에서 거울 사용 개수가 더 크면 재설정할 필요가 있다고 봄

2. 거울을 놓으면 진행방향이 바뀜
   남OR북 <-> 동OR서

코드

#include <iostream>
#include <algorithm>
#include <string>
#include <queue>
#include <vector>
#define INF 987654321
using namespace std;
int n, sy, sx, ey, ex, ret = INF;
string map[51];
vector<pair<int, int>> v;
queue<pair<pair<int, int>, pair<int, int>>> q;
int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
int checked[51][51][4];
int isValid(int y, int x)
{
    return (y >= 0 && x >= 0 && y < n && x < n && map[y][x] != '*');
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> map[i];

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (map[i][j] == '#')
                v.push_back({i, j});
        }
    }

    sy = v[0].first;
    sx = v[0].second;
    ey = v[1].first;
    ex = v[1].second;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            for (int k = 0; k < 4; k++)
                checked[i][j][k] = INF;

    for (int i = 0; i < 4; i++)
    {
        q.push({{sy, sx}, {i, 0}});
        checked[sy][sx][i] = 0;
    }

    while (!q.empty())
    {
        int y = q.front().first.first;
        int x = q.front().first.second;
        int d = q.front().second.first;
        int cnt = q.front().second.second;
        q.pop();

        if (y == ey && x == ex)
            ret = min(ret, cnt);

        int ny = y + dir[d][0];
        int nx = x + dir[d][1];

        if (isValid(ny, nx))
        {
            if (checked[ny][nx][d] > cnt)
            {
                q.push({{ny, nx}, {d, cnt}});
                checked[ny][nx][d] = cnt;
            }

            if (map[ny][nx] == '!')
            {
                if (d == 0 || d == 1)
                {
                    for (int j = 2; j <= 3; j++)
                    {
                        if (checked[ny][nx][j] > cnt + 1)
                        {
                            checked[ny][nx][j] = cnt + 1;
                            q.push({{ny, nx}, {j, cnt + 1}});
                        }
                    }
                }

                else if (d == 2 || d == 3)
                {
                    for (int j = 0; j <= 1; j++)
                    {
                        if (checked[ny][nx][j] > cnt + 1)
                        {
                            checked[ny][nx][j] = cnt + 1;
                            q.push({{ny, nx}, {j, cnt + 1}});
                        }
                    }
                }
            }
        }
    }
    cout << ret;
}