6087번 레이저 통신

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

나중에 다시 풀어 볼 문제이다.

만만하게 봤다가 큰 코 다친 문제이다.

단순히 거울의 개수가 더 적을 때, 갱신만 해주면 되는 줄 알았는데, 그게 아니었다.

우선 신경써야할 것은

while(!q.empty()){}에는 어떠한 종료 조건을 넣어서는 안 되고,

방향을 제대로 활용해야하며(dx, dy, i, direct 등),

88번 째 줄을 조심해야 한다.

또한, 본격적인 BFS 전에 출발지점에서 4가지 방향을 모두 queue에 넣어줘야한다.

계속 예제와 질문게시판의 반례가 해결되지 않아서

다른 분의 코드를 참고하였다.

몇 시간 동안 붙잡고 있었는지 모르겠다. 최소 8시간 인 듯 하다.

88번 째 줄은 아래와 같은 예제 때문에 >=로 써줘야 한다.

(행, 열)

2 3

.C

..

C*

(1, 0)에는 (0, 1)에서 출발한 것이 동시에 도착해있다.

하나는 거울의 개수가 1, 또 다른 하나도 거울의 개수가 1이지만,

(0, 1)에서 아래로 출발한 것이 (1, 0)에 먼저 도착해있을 경우, (0, 0)에서 아래로 오는 것은 >로 할 경우 갱신 및 queue에 push가 안 된다.

또한, (0, 1)에서 아래로 출발한 것은 (2, 0)에 도착하면 거울의 개수가 2개가 되어버리기 때문에

(1, 0)에서 거울의 개수가 같은 1일 때도, 처리해줘야 하므로,

'='을 포함하여, '<='로 입력한다.

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
#include <set>
#include <sstream>
#include <tuple>
 
#pragma warning(disable:4996)  
#pragma comment(linker, "/STACK:336777216")
 
using namespace std;
 
// https://www.acmicpc.net/problem/6087
 
typedef struct info
{
    int y;
    int x;
    int direct;
    int mirror;
}info;
 
int W = 0, H = 0;
 
char Map[102][102];
 
int dy[4] = { 0, 1, 0, -1 };
int dx[4] = { 1, 0, -1, 0 };
//   direct = 0  1  2   3
 
queue<info> q;
 
info temp;
 
int mirror[102][102] = { 0, };
 
pair<int, int> laser[2];
 
int BFS()
{
    for (int i = 0; i < 4; i++)
    {
        temp.y = laser[0].first;
        temp.x = laser[0].second;
        temp.direct = i;
        temp.mirror = 0;
 
        q.push(temp);
    }
 
    mirror[laser[0].first][laser[0].second] = 0;
 
    while (!q.empty())
    {
        int qSize = q.size();
 
        while (qSize--)
        {
            int r = q.front().y;
            int c = q.front().x;
            int d = q.front().direct;
            int m = q.front().mirror;
 
            q.pop();
 
            printf("\n\n");
 
            for (int i = 0; i < 4; i++)
            {
                int y = r + dy[i];
                int x = c + dx[i];
                int nm = m; 
                // m을 계속 활용해야 하는데,
                // m을 변화시키지 않고, 다른 변수를 활용해야한다.
                // m만 쓰면 다음 for문의 i 변수에 의해 변화된 m의 값이 활용되어버린다.
 
                if (y < 0 || y >= H | x < 0 || x >= W || Map[y][x] == '*') continue;
 
                if (d != i) ++nm;            
 
                if (mirror[y][x] >= nm) // '>'가 아니다.
                {
                    mirror[y][x] = nm;
 
                    temp.y = y;
                    temp.x = x;
                    temp.direct = i;
                    temp.mirror = nm;
 
                    q.push(temp);
                }
            }    
        }
    }
 
    return mirror[laser[1].first][laser[1].second];
}
 
int main(void)
{
    int idx = 0;
 
    scanf("%d %d", &W, &H);
 
    for (int i = 0; i < H; i++)
    {
        for (int j = 0; j < W; j++)
        {
            cin >> Map[i][j];
 
            if (Map[i][j] == 'C')
            {
                laser[idx].first = i;
                laser[idx++].second = j;
            }
 
            mirror[i][j] = 102 * 102;
        }
    }
 
    printf("%d\n", BFS());
 
    return 0;
}