백준 6087 / 레이저 통신

하다가 로직이 너무 무식한데? 싶으면 빨리빨리 손절하고 다시 세우자

최단경로가 아닌 방향을 최소 몇번 꺾어야 되는지 묻는 문제이다.

방법이 도무지 떠오르지 않아 다른 사람들의 코드를 참고했다. (ㅠㅠ)

로직은 이렇다.

첫번째 C(시작점)에서 4방향으로 벽이나 밖에 부딪힐때까지 선을 긋는다. (선을 그으면서 dist를 체크해준다.)

선이 그어진 부분에서 다시 4방향으로 선을 긋는다. (이미 선이 그어진 곳이라면 긋지 않는다.)

이를 반복하면 갈 수 있는 모든 빈칸에 dist가 체크되는데

도착점의 dist에서 1를 빼주면 답이다.

결국 거울의 개수를 생각하면서 푸는 문제가 아닌,

몇번의 직선으로 도착점에 도달할 수 있는 가에 대한 문제로 생각해서 풀면 더욱 쉽다.

코드

#include<stdio.h>
#include<iostream>
#include<vector>
#include<queue>
#include<tuple>
#include<memory.h>
 
using namespace std;
 
char map[101][101];
int dist[101][101];
 
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
 
int main() {
 
    //freopen("Text.txt", "r", stdin);
 
    int n, m;
 
    cin >> m >> n;
 
    memset(dist, -1, sizeof(dist));
 
    bool find = false;
    int sx, sy;
    int fx, fy;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> map[i][j];
            if (map[i][j] == 'C' && find == false) {
                find = true;
                sx = i;
                sy = j;
            }
            if (map[i][j] == 'C'&& find == true) {
                fx = i;
                fy = j;
            }
        }
    }
 
    queue<tuple<int, int, int>>q;
 
    dist[sx][sy] = 1;
 
    q.push({ sx,sy,1 });
 
    while (!q.empty()) {
        int x, y, cnt;
        tie(x, y, cnt) = q.front();
        q.pop();
        
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            while (nx >= 0 && nx < n && ny >= 0 && ny < m) {
                if (map[nx][ny] == '*')break;
                else {
                    if (dist[nx][ny] == -1) {
                        dist[nx][ny] = cnt;
                        q.push({ nx,ny,cnt + 1 });
                    }
                }
                nx += dx[i];
                ny += dy[i];
            }
        }
    }
    cout << dist[fx][fy] - 1 << endl;
}