uang's blog

 풀이 방법

이 문제는 두 지점 사이의 최소 거울 수를 구하는 문제로, 평소 두 지점의 최단거리를 구할 때 사용하는 BFS 를 응용해 "거리" 대신 "거울 수(방향 전환이 일어나는 수)" 를 사용하여 풀 수 있다고 생각했다.

단순 좌표 (y, x) 뿐만 아니라, 사용된 거울 수 및 이동해온 방향 정보가 필요하므로 새로운 구조체를 정의한다.

struct cell{
    int y, x, num, p_dir;
    cell(int y,int x,int num, int p_dir):y(y), x(x), num(num), p_dir(p_dir) {};
};

이동해온 방향(p_dir)을 저장하는 이유는 거울이 사용되는 지점이 방향이 전환되는 시점이기 때문에, 현재 좌표가 어느 방향에서 왔는지 확인하기 위해 필요하다.

이 구조체를 이용해 사용된 거울 수(num) 이 가장 작은 순으로 queue 에서 가져오기 위해 우선순위 큐를 사용한다.

 우선순위 큐의 Comparator 정의

내가 정의한 구조체에서 max-heap 으로 사용할지  min-heap 으로 사용하지 결정하기 위해 compartor를 정의해야 한다.

방법은 구사과 님의 블로그에 자세히 설명돼있다.

풀이에 사용된 방법은 구조체를 이용해 operator() 를 정의해 사용했다.

struct cmp{
    bool operator()(const struct cell& a, const struct cell& b){
        return a.num > b.num;
    }
};

// 중략

priority_queue< cell, vector<cell>, cmp > pq;

* 참고로 greater 는 작은 값을 먼저, less 는 큰 값을 먼저 리턴한다.

* a.num > b.num 는 greater 와 같고, a.num < b.num 은 less 와 같다.

이렇게 정의된 우선순위 큐를 이용하면, 시작지점에서 거울을 사용하지 않고 최대한 이동하여 탐색한 후,

거울  1개, 2개, k개 사용해서 이동할 수 있는 위치를 순차적으로 탐색할 수 있다.

 소스코드

#include<stdio.h>
#include<vector>
#include<queue>
 
using namespace std;
 
struct cell{
    int y, x, num, p_dir;
    cell(int y,int x,int num, int p_dir):y(y), x(x), num(num), p_dir(p_dir) {};
};
struct cmp{
    bool operator()(const struct cell& a, const struct cell& b){
        return a.num > b.num;
    }
};
 
/*
bool operator<(const struct cell a, const strcut cell b){
    return a.num > b.num;
}
*/
int w,h, sy=-1,sx=-1, dy,dx;
int dix[4] = {-1,1,0,0}, diy[4] = {0,0, -1, 1};
char board[111][111];
bool visited[111][111];
bool dir_check(int a, int b){
    return (a<2 && b<2) || (a>=2 && b>=2)  || a == -1;
}
int main(){
    scanf("%d%d",&w,&h);
 
    for(int i=0;i<h;i++){
        scanf("%s", board[i]);
        for(int j=0;j<w;j++){
            if(board[i][j] == 'C'){
                if(sy != -1 && sx != -1){
                    dy = i, dx = j;
                } else {
                    sy = i, sx  = j;
                }
            }
        }
    }
    priority_queue< cell, vector<cell>, cmp > pq;
    // priority_queue< cell, vector<cell>, greater<cell> > pq;
 
    pq.push(cell(sy, sx, 0, -1));
    while(!pq.empty()){
        cell cur = pq.top();
        pq.pop();
        visited[cur.y][cur.x] = 1;
        if(cur.y == dy && cur.x == dx){
            printf("%d\n", cur.num);
            break;
        }
        for(int i=0;i<4;i++){
            int ny = cur.y + diy[i], nx = cur.x + dix[i];
            if(ny >=0 && nx >=0 && nx < w && ny < h) {
                if(!visited[ny][nx] && board[ny][nx] != '*'){
                    // printf("\tnext : (%d, %d) num : %d, is_plus? : %d\n", ny,nx, cur.num, !dir_check(cur.p_dir, i));
                    pq.push(cell(ny, nx, cur.num + (dir_check(cur.p_dir, i) ? 0 : 1), i));
                }
            }
        }
    }
    return 0;
}