6087 / 레이저 통신

레이저 통신 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	128 MB	338	88	61	25.311%

문제

크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다.

'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 설치해야 하는 거울 개수의 최솟값을 구하는 프로그램을 작성하시오. 레이저로 통신한다는 것은 두 칸을 레이저로 연결할 수 있음을 의미한다.

레이저는 C에서만 발사할 수 있고, 빈 칸에 거울('/', '\')을 설치해서 방향을 90도 회전시킬 수 있다. 

아래 그림은 H = 8, W = 7인 경우이고, 빈 칸은 '.', 벽은 '*'로 나타냈다. 왼쪽은 초기 상태, 오른쪽은 최소 개수의 거울을 사용해서 두 'C'를 연결한 것이다.

7 . . . . . . .         7 . . . . . . .
6 . . . . . . C         6 . . . . . /-C
5 . . . . . . *         5 . . . . . | *
4 * * * * * . *         4 * * * * * | *
3 . . . . * . .         3 . . . . * | .
2 . . . . * . .         2 . . . . * | .
1 . C . . * . .         1 . C . . * | .
0 . . . . . . .         0 . \-------/ .
  0 1 2 3 4 5 6           0 1 2 3 4 5 6

입력

첫째 줄에 W와 H가 주어진다. (1 ≤ W, H ≤ 100)

둘째 줄부터 H개의 줄에 지도가 주어진다. 지도의 각 문자가 의미하는 것은 다음과 같다.

• .: 빈 칸
• *: 벽
• C: 레이저로 연결해야 하는 칸

'C'는 항상 두 개이고, 레이저로 연결할 수 있는 입력만 주어진다.

출력

첫째 줄에 C를 연결하기 위해 설치해야 하는 거울 개수의 최솟값을 출력한다.

---

즐거운 추석. 할거 없을땐 백준을 풀자.

불과 6개월전만해도 풀기 싫어했지만, 이번에는 꼭 풀자는 생각을 갖고 풀어보았다.

심지어 구글링해도 안나오니까 내가 쓴걸로 누군가에게 도움이 됐으면 좋겠다.

로직은 다음과 같다.

1. 레이저 두 개의 위치는 벡터에 넣는데, 첫 번째 레이저랑 두 번째 레이저 어디에서 시작하든 상관 없다.

2. 이전에 [1261 / 알고스팟] 이랑 똑같은 방식인거 같아서 비슷하게 풀어보려고 했다.

3. 레이저는 4가지 방향으로 뻗어나가는 BFS방식을 따르되, 가다가 방향이 바뀌는 경우는 거울에 반사된 것으로간주하여 횟수를 늘려준다. 이 때, 늘려준 횟수와 check배열에 저장된 값을 비교해서 늘려준 횟수가 더 큰 경우는 굳이 반사 안해도 여기는 올 수 있음을 의미한다고 여겨서 Q에 push하지 않는다. 그 반대의 경우는 check배열을 갱신하고 횟수를 늘려서 Q에 저장해준다.

4. 3을 반복해서 마지막 레이저의 위치를 찾아준다. 끝!

[Code]

#include<iostream>
#include<queue>
#include<vector>
#define P pair<int,int>
#define PI pair<P,int>
#define PP pair<P,P>
#define mp(a,b) make_pair(a,b)
#define mp3(a,b,c) mp(mp(a,b),c)
#define mp4(a,b,c,d) mp(mp(a,b),mp(c,d))
using namespace std;
 
char map[102][102];
 
// 1 북, 2 동, 3 남, 4 서
int W, H, check[102][102], xx[] = { -1,0,1,0 }, yy[] = { 0,1,0,-1 };
 
vector<P> Lazer;
 
int bfs();
 
int main() {
 
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
 
    cin >> H >> W;
 
    for (int i = 0; i < W; i++) {
        cin >> map[i];
        for (int j = 0; j < H; j++) {
            if (map[i][j] == 'C') Lazer.push_back(mp(i, j));
            check[i][j] = TMP_MAX;
        }
    }
 
    check[Lazer[0].first][Lazer[0].second] = 0;
 
    cout << bfs() << endl;
 
    return 0;
}
 
int bfs() {
    queue<PP> Q;
 
    // ff : x, fs : y, sf : count, ss : dir
    for (int i = 0; i < 4; i++) Q.push(mp4(Lazer[0].first, Lazer[0].second, 0, i));
 
    while (!Q.empty()) {
        int cx = Q.front().first.first, cy = Q.front().first.second;
        int cnt = Q.front().second.first, dir = Q.front().second.second;
        Q.pop();
 
        for (int i = 0; i < 4; i++) {
            int nx = cx + xx[i], ny = cy + yy[i], next_cnt = cnt;
            if (nx < 0 || ny < 0 || nx > W - 1 || ny > H - 1 || map[nx][ny]=='*') continue;
            if (dir != i) next_cnt += 1;
 
            if (check[nx][ny] >= next_cnt) {
                check[nx][ny] = next_cnt;
                Q.push(mp4(nx, ny, next_cnt, i));
            }
        }
    }
    return check[Lazer[1].first][Lazer[1].second];
}

여담 ) 이해가 안되신다면 댓글을 달아주십쇼.