[백준 6087] 레이져 통신

[백준 6087] 레이져 통신

문제 링크

#include "header.h"
using namespace std;
int W, H;
int ans = 987654321;
char map_[101][101];
int dist[101][101];
int visit[101][101];
vector<pair<int, int>> C;
int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};
void input() {
    cin >> W >> H;
    for (int i = 0; i < H; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < s.length(); j++) {
            map_[i][j] = s[j];
            if (map_[i][j] == 'C') {
                C.push_back({i, j});
            }
        }
    }
}

void solve() {
    int start_x = C[0].first;
    int start_y = C[0].second;

    int dest_x = C[1].first;
    int dest_y = C[1].second;

    queue <pair<int, int>> q;
    q.push({start_x, start_y}); // 시작점 넣기
    visit[start_x][start_y] = 1;
    dist[start_x][start_y] = 0;

    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];

            while(map_[nx][ny] != '*' && nx >=0 && ny >=0 && nx < H && ny < W){
                if(!visit[nx][ny]){
                    visit[nx][ny] = 1;
                    dist[nx][ny] = dist[x][y] + 1;
                    q.push({nx, ny});
                }
                nx += dx[i];
                ny += dy[i];
            }

        }
    }

    //꺾인 수이기 때문에 -1 해주어야 함!
    cout << dist[dest_x][dest_y] -1 << endl;
}
int main() {
    input();
    solve();

    return 0;
}

• bfs 좀만 꽈도 못푸는 나 :)..
• 처음엔 삼차원 배열로 상, 하, 좌, 우의 경우도 탐색 해주었는데, 잘 안됐다.
• 그래서 갈 수 있는 직선을 모두 탐색하고, 방향 전환해 주는 식으로 풀었다.
• dist에 몇 번 꺾었는지를 표시 해 준다. dist[nx][ny] = dist[x][y] + 1
• 최종 답은 도착 좌표의 dist값에서 -1을 해 주어야 한다. 꺾인 횟수니까 거울의 갯수는 꺾인 수 - 1이기 때문이다.