레이저 통신

문제 분석 및 풀이

설계 분석

• 벽 부수고 지나가기처럼 BFS에 상태를 추가하는 문제태를 추가하는 문제
• $N<100$ 이므로 $O(N^3)$까지 가능
• BFS진행
  • 각 Cell에 어느 방향으로 들어왔는지, 거울 개수는 몇개인지 기록
  • 직전 Cell의 진입 방향과 다음 방향이 다르면 거울 개수 증가

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_map>
#include <cstring>
#include <queue>
using namespace std;

int W, H;
const int INF = 987654321;
struct Pos
{
    int x;
    int y;
    int dir;
    int cnt;

    bool operator==(Pos& other)
    {
        return x==other.x && y==other.y; 
    }

    bool operator<(const Pos& other) const
    {
        return cnt < other.cnt;
    }
};

vector<string> graph;
vector<vector<vector<int>>> visited;
vector<Pos> ans;
vector<Pos> C;

bool CanGo(Pos nextPos)
{
    int x = nextPos.x;
    int y = nextPos.y;
    int dir = nextPos.dir;

    if (x < 0 || x >= H) return false;
    if (y < 0 || y >= W) return false;
    if (graph[x][y] == '*') return false;
    if (visited[x][y][dir] <= nextPos.cnt) return false;

    return true;
}

void BFS(Pos start)
{
    int dx[4] = {1, 0, -1, 0};
    int dy[4] = {0, 1, 0, -1};

    queue<Pos> q;
    q.push({start.x, start.y, -1, 0});

    for (int i=0; i<4; i++)
    visited[start.x][start.y][i] = 0;

    while (!q.empty())
    {
        Pos curr = q.front(); q.pop();
        for (int i=0; i<4; i++)
        {
            int cnt = curr.cnt;
            // 직전 방향과 다르면 거울증가 (90도 꺾이는 경우, 180도 또한 여기 걸리는데 최소 값에서 걸러짐)
            if (curr.dir != -1 && i != curr.dir) cnt++;
            Pos nextPos = {curr.x + dx[i], curr.y + dy[i], i, cnt};
            if (CanGo(nextPos))
            {
                visited[nextPos.x][nextPos.y][nextPos.dir] = cnt;
                q.push(nextPos);
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> W >> H;
    graph = vector<string>(H, string(W,' '));
    visited = vector<vector<vector<int>>>(H,vector<vector<int>>(W, vector<int>(4,INF)));

	// 격자 그래프 입력
    for (int i=0; i<H; i++)
    {
        for (int j=0; j<W; j++)
        {
            char cell;
            cin >> cell;
            // 레이저의 출발, 도달 기록
            if (cell == 'C')
            {
                C.push_back({i,j,0});
            }
            graph[i][j] = cell;
        }
    }

    BFS(C.front());

	// 4방향으로 들어온 경로중에서 가장 적은 거울을 사용한 경우를 선택
    auto minVal = *min_element(visited[C.back().x][C.back().y].begin(), visited[C.back().x][C.back().y].end());

    cout << minVal;

    return 0;
}