문제

레이저 통신 성공다국어

한국어

문제
크기가 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를 연결하기 위해 설치해야 하는 거울 개수의 최솟값을 출력한다.

풀이

근래 푼 문제중에 제일많이 틀렸다.

최소개수의 거울 을 구하는 것이 목표이고 출발지와 목적지에 해당하는 좌표가 정해져 있기 때문에 거울의 개수를 기준으로한 BFS를 사용하여 문제를 풀었다.

거울의 개수를 기준으로 하기 때문에 가중치는 항상 0, 1이다. 최단거리와는 관계가 없이 거울을 가장 적게 사용한 경로 기준 이기 때문에 각각의 경로 부분에 방향정보를 같이 저장하여 방향이 바뀌었다면 거울의 개수 + 1을 해주도록 하였다.

중복 방문에 대해서도 체크해주어야 하는데 재방문시에 해당 노드에 표시된 방향정보, 거울의 개수 가 같다면 그 노드는 다시 방문하지 않아도 된다.

코드

#include <iostream>
#include <queue>
#include <algorithm>
#include <string>
#include <deque>
#define INTMAX 987654321
using namespace std;
int W, H, dx[4]={1,0,-1,0}, dy[4]={0,1,0,-1}, ans[101][101], dirList[101][101][4];
// 하 -> 0, 우 -> 1, 상 -> 2, 좌 -> 3
vector<pair<int,int > > C;
string board[101];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>W>>H;
    for(int i=0; i<H; i++)
        cin>>board[i];
    for(int i=0; i<H; i++){
        for(int j=0; j<W; j++){
            if(board[i][j] == 'C'){
                C.push_back(make_pair(i,j));
            }
            ans[i][j] = INTMAX;
        }
    }
    ans[C[0].first][C[0].second] = 0;
    queue<pair<pair<int,int >,pair<int,int> > >q;
    for(int i=0; i<4; i++) {
        int nx = C[0].first+dx[i];
        int ny = C[0].second+dy[i];
        if(nx<0 || nx >= H || ny < 0 || ny >= W) continue;
        if(board[nx][ny] == '*') continue;
        ans[nx][ny] = 0;
        dirList[nx][ny][i] = 1;
        q.push(make_pair(make_pair(nx, ny), make_pair(i, 0)));
    }
    while(!q.empty()) {
        auto cur = q.front(); q.pop();
        for(int i=0; i<4; i++) {
            int nx = cur.first.first + dx[i];
            int ny = cur.first.second + dy[i];
            int tmp = cur.second.second;
            if(nx<0 || nx >= H || ny < 0 || ny >= W) continue;
            if(board[nx][ny] == '*') continue;
            if(i == cur.second.first && (i+2)%4 == cur.second.first) continue;
            if(i != cur.second.first) tmp += 1;
            if(ans[nx][ny] == tmp && dirList[nx][ny][i] == 1) continue;
            if(ans[nx][ny] >= tmp) {
                dirList[nx][ny][i] = 1;
                ans[nx][ny] = tmp;
                q.push(make_pair(make_pair(nx, ny), make_pair(i, tmp)));
            }
        }
    }
    cout<<ans[C[1].first][C[1].second];
}