[BOJ-2151]거울설치

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

[풀이방법]

BFS로 풀이할 수 있었다.

BFS로 visited 를 구성할 때 [current_dir][row][col] 로 구성을 하며 

[current_dir][r][c] : [r][c] 위치에 [current_dir]  방향(상하좌우)으로 들어온 경우가 있는 경우이다.

처음 시작하는 문부터 BFS를 실시한다. 

[위치] = [tr][tc] 라고 하자.

초기값으로 [상하좌우][문의위치] 의 처음 거울의 설치 갯수는 0이다. 

총 4개의 정보를 큐에 넣고 탐색을 진행한다. 현재 들어온 방향을 기준으로 [current_dir][다음위치]

1. current_dir으로 진행한다.
2. '*' 더이상 진행할 수 없는 경우
3. '!' 거울을 설치할 수 있는 위치에서 경우의 수는
1.  현재진행한 방향으로 그대로 진행하는 경우
2. 45도로 왼쪽으로 진행하는 경우
3. 45도로 오른쪽으로 진행하는 경우
4. '.' 그대로 진행한다. 방향이 변하지 않음.
5. '#' 인 경우 해당 값 중 최소값을 저장.

위의 진행 순서로 BFS를 진행하면 된다. 

[C++11]

#include<cstdio>
#include<queue>
using namespace std;
const int m = 55;
const int dr[] = { 1,0,-1,0 };
const int dc[] = { 0,1,0,-1 }; // down right up left
const int INF = 1 << 22;
char im[m][m];
int vis[4][m][m];
struct pos {
    int r, c;
    int current_dir;
    pos() {}
    pos(int ir, int ic, int icd) : r(ir), c(ic), current_dir(icd) {}
    void set_pos(int ir, int ic) {
        r = ir;
        c = ic;
    }
};
int main() {
    int n;
    scanf("%d", &n);
    pos start, end;
    bool is_start = false;
    for (int r = 0; r < n; r++) {
        scanf("%s", im[r]);
        for (int c = 0; c < n; c++) {
            if (im[r][c] == '#') {
                if(!is_start) is_start = true, start.set_pos(r, c);
                else if (is_start) end.set_pos(r, c);
            }
        }
    }
    queue<pos> Q;
    for (int i = 0; i < 4; i++) {
        Q.push(pos(start.r, start.c, i));
        for (int r = 0; r < n; r++) {
            for (int c = 0; c < n; c++) {
                vis[i][r][c] = INF;
            }
        }
        vis[i][start.r][start.c] = 0;
    } // INF;
    
    while (!Q.empty()) {
        pos here = Q.front();
        Q.pop();
        int hr = here.r;
        int hc = here.c;
        int hd = here.current_dir;
        int tr = here.r + dr[hd];
        int tc = here.c + dc[hd];
        if (tr < 0 || n <= tr || tc < 0 || n <= tc) continue;
        if (im[tr][tc] == '*')continue;
        if (im[tr][tc] == '!') {
            if (vis[hd][tr][tc] > vis[hd][hr][hc]) {
                vis[hd][tr][tc] = vis[hd][hr][hc]; // 설치 X
                Q.push(pos(tr, tc, hd)); // 그방향 그대로 간다.
            }
            if (vis[(hd + 1) % 4][tr][tc] > vis[hd][hr][hc] + 1) {
                vis[(hd + 1) % 4][tr][tc] = vis[hd][hr][hc] + 1;
                Q.push(pos(tr, tc, (hd + 1) % 4)); // 45도 +1
            }
            if (vis[(hd + 3) % 4][tr][tc] > vis[hd][hr][hc] + 1) {
                vis[(hd + 3) % 4][tr][tc] = vis[hd][hr][hc] + 1;
                Q.push(pos(tr, tc, (hd + 3) % 4)); // 45도 +1
            }
        }
        else if (im[tr][tc] == '.') {
            if (vis[hd][tr][tc] > vis[hd][hr][hc]) {
                vis[hd][tr][tc] = vis[hd][hr][hc];
                Q.push(pos(tr, tc, hd)); // 그방향 그대로 간다.
            }
        }
        else if (im[tr][tc] == '#') {
            if (vis[hd][tr][tc] > vis[hd][hr][hc]) {
                vis[hd][tr][tc] = vis[hd][hr][hc];
            }
        }
    }
    
    int ans = INF;
    for (int i = 0; i < 4; i++) {
        if (ans > vis[i][end.r][end.c]) {
            ans = vis[i][end.r][end.c];
        }
    }
    printf("%d\n", ans);
    return 0;
}
// 7% WA
// 15% WA?
// 23% WA