[Algorithm] Baekjoon 6087번 : 레이저 통신

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

 

 

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_set>
 
using namespace std;
 
 
 
 
 
int w, h;
char arr[101][101] = { 0 };
int dirs[4][2] = { {-1,0}, {1,0}, {0,-1}, {0,1} };
vector<pair<int, int>> points;
int visited[101][101][4] = { 0 };
const int maxNum = 0x3f3f3f3f;
 
int GetReverseDir(int dir)
{
    switch (dir)
    {
    case 0: return 1;
    case 1: return 0;
    case 2: return 3;
    case 3: return 2;
    default:return -1;
    }
}
 
bool IsValidPath(int y, int x)
{
    if (y < 0 || y == h) return false;
    if (x < 0 || x == w) return false;
    if (arr[y][x] == '*') return false;
 
    return true;
}
 
struct Node
{
    int y;
    int x;
    int dir;
    int mirrorCount;
};
 
int BFS(int startY, int startX)
{
    memset(visited, 0x3f, sizeof(visited));
    int answer = maxNum;
    queue<Node> q;
 
    visited[startY][startX][0] = visited[startY][startX][1] =
        visited[startY][startX][2] = visited[startY][startX][3] = 0;
 
 
    for (int i = 0; i < 4; ++i)
    {
        int nextY = startY + dirs[i][0];
        int nextX = startX + dirs[i][1];
 
        if (!IsValidPath(nextY, nextX)) continue;
 
        visited[nextY][nextX][GetReverseDir(i)] = 0;
        q.push({ nextY,nextX,i,0 });
    }
 
    while (!q.empty())
    {
        int curY = q.front().y;
        int curX = q.front().x;
        int curDir = q.front().dir;
        int curMirrorCount = q.front().mirrorCount;
 
        q.pop();
 
        if (curY == points[1].first && curX == points[1].second)
        {
            answer = min(answer, curMirrorCount);
            continue;
        }
 
        for (int i = 0; i < 4; ++i)
        {
            int nextY = curY + dirs[i][0];
            int nextX = curX + dirs[i][1];
 
            if (!IsValidPath(nextY, nextX)) continue; // 범위, 벽체크
            if (i == GetReverseDir(curDir)) continue; // 왔던방향이면 다시 갈필요없음.
 
            if ((curDir < 2 && i > 1) || (curDir > 1 && i < 2)) // 가려는 방향이 90도회전이라 거울을 설치해야한다면
            {
                if (curMirrorCount + 1 < visited[nextY][nextX][GetReverseDir(i)]) 
                {
                    visited[nextY][nextX][GetReverseDir(i)] = curMirrorCount + 1;
                    q.push({ nextY,nextX, i, curMirrorCount + 1 });
                }
            }
            else
            {
                if (curMirrorCount < visited[nextY][nextX][GetReverseDir(i)])
                {
                    visited[nextY][nextX][GetReverseDir(i)] = curMirrorCount;
                    q.push({ nextY,nextX, i, curMirrorCount });
                }
            }
        }
    }
 
    return answer;
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> w >> h;
 
    for (int i = 0; i < h; ++i)
    {
        for (int j = 0; j < w; ++j)
        {
            cin >> arr[i][j];
 
            if (arr[i][j] == 'C')
            {
                points.push_back({ i,j });
            }
        }
    }
 
    cout << BFS(points[0].first, points[0].second);
}
 
 

 

 

알고리즘문제를 좀 꾸준히 풀었으면 20분내에도 풀었을텐데... 정답률에 비해서는 그렇게 어렵지 않았다.

BFS로 풀었는데, 중요한점은 방문체크를 할 때 각 방향에 대해서 해야한다는 것.

그래서 visited[101][101][4] == visited[y][x][dir]이다.

 

처음에 큐에 노드를 넣을때도 4개를 넣어야 한다. 레이저는 맨 처음 아무비용없이 각 방향으로 쏠 수 있기 때문이다.

노드를 뿌릴때는 뻗어나가려는 방향에 대해서 이전에 이미 더 적은값으로 방문했는지 체크 후, 뻗어나가면 된다.

90도 회전해야하면 +1을 해서 비교하고, 뻗어나가려는 방향이면 그냥  비교하면 된다.