거울 설치

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

2151번: 거울 설치

#include<iostream>
#include<queue>
 
using namespace std;
 
int n;
string map[50];
int sx, sy, ex, ey;
int dx[] = { 0,0,1,-1 }; int dy[] = { 1,-1,0,0 };
bool d[50][50]; int dist[50][50];
 
struct info {
    int x, y, cnt, dir;
    info(int x, int y, int cnt, int dir) {
        this->x = x;
        this->y = y;
        this->cnt = cnt;
        this->dir = dir;
    }
};
 
void bfs() {
    queue<info> q;
    for (int i = 0; i < 4; i++) {
        int nx = sx + dx[i]; int ny = sy + dy[i];
        if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
        if (map[nx][ny] == '*') continue;
        q.push(info(sx, sy, 0, i));
    }
    d[sx][sy] = true;
    while (!q.empty()) {
        
        int x = q.front().x; int y = q.front().y; int cnt = q.front().cnt; int dir = q.front().dir;
        q.pop(); //cout << x << ' ' << y << ' ' <<dir<< endl;
        int nx = x; int ny = y;
        for (int i = 0; i < n; i++) {
            nx += dx[dir]; ny += dy[dir];
            if (nx < 0 || nx >= n || ny < 0 || ny >= n) break;
            if (map[nx][ny] == '*') break;
            if (d[nx][ny] == false) {
                d[nx][ny] = true;
                dist[nx][ny] = cnt;
                if (map[nx][ny] == '.') {
                    q.push(info(nx, ny, cnt, dir));
                }
                if (map[nx][ny] == '!') {
                    for (int j = 0; j < 4; j++) {
                        if (dir == j) continue;
                        if (dir == 0 && j == 1) continue;
                        if (dir == 1 && j == 0) continue;
                        if (dir == 2 && j == 3) continue;
                        if (dir == 3 && j == 2)continue;
                        q.push(info(nx, ny, cnt + 1, j));
                        }
                    }        
            }
            else if(d[nx][ny]){
                if (dist[nx][ny] > cnt) {
                    dist[nx][ny] = cnt;
                    if (map[nx][ny] == '.') {
                        q.push(info(nx, ny, cnt, dir));
                    }
                    if (map[nx][ny] == '!') {
                        for (int j = 0; j < 4; j++) {
                            if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
                            if (dir == j) continue;
                            if (dir == 0 && j == 1) continue;
                            if (dir == 1 && j == 0) continue;
                            if (dir == 2 && j == 3) continue;
                            if (dir == 3 && j == 2)continue;
                            q.push(info(nx, ny, cnt + 1, j));
                        }
                    }
                }
            }
        }
        
    }
 
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> map[i];
    }
    int trash = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (map[i][j] == '#') {
                if (trash == 0) {
                    sx = i; sy = j;
                }
                else {
                    ex = i; ey = j;
                }
 
                trash++;
                if (trash == 2) break;
            }
        }
    }
    bfs();
    /*for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << dist[i][j] << ' ';
        }cout << '\n';
    }*/
    cout << dist[ex][ey] << '\n';
    return 0;
}

BFS문제다.

로봇, 레이저통신 문제랑 비슷한 풀이인데, 방향성 + BFS의 문제가 아닌가싶다.

딱히 주의할점은 없는듯 굉장히 직관적인문제