[백준/C++] 6087번 레이저 통신

백준

---

🤔문제 이해

하나의 C에서 다른 C까지 가는 경로 중 방향을 가장 적게 바꾸면서 가는 방법을 찾아 방향을 바꾼 횟수를 출력하는 문제이다.

---

🔥풀이🔥

첫번째 C에서 갈 수 있는 경로를 먼저 탐색하여 각 방향별로 cnt를 0으로 queue에 넣어준다.

그 뒤에는 queue가 빌때까지 각 방향대로 돌면서 이전과 같은 방향인 경우 cnt는 그대로 두고, 다른 방향인 경우 cnt에 +1을 해주었다. 그렇게 처리한 cnt값이 dp의 값보다 작거나 같으면 dp를 업데이트해주고 queue에도 넣어주었다. 

queue에서 pop될 때 dp의 값이 cnt보다 작으면 continue을 해주어서 불필요한 연산을 줄여주었고, dp값이 cnt보다 큰 경우는 cnt로 업데이트 해주었다. 

 

✍️ 후기

처음엔 단순히 BFS를 해서 방향이 바뀔 때마다 cnt값을 +1해주는 방식으로 했지만 이렇게 하면 메모리 초과가 났다. 

---

#include <queue>
#include <iostream>

#define INF 1000000000

using namespace std;

int w, h;
char map[101][101];
int dp[101][101];
priority_queue<pair<pair<int, int>, pair<int, int>>> pq;
pair<int, int> start;
pair<int, int> ended;
int di[4] = {1, -1, 0, 0};
int dj[4] = {0, 0, 1, -1};


void BFS() {

    while (!pq.empty()) {
        int cnt = -pq.top().first.first;
        int direct = pq.top().first.second;
        int i = pq.top().second.first;
        int j = pq.top().second.second;
        pq.pop();

        if( dp[i][j] < cnt ) continue;
        dp[i][j] = cnt;
        
        for (int k = 0; k < 4; k++) {
            int ni = i + di[k];
            int nj = j + dj[k];
            if (ni < 0 || nj < 0 || ni >= h || nj >= w) continue;
            if (map[ni][nj] == '*') continue;

            int next_cnt = (direct == k) ? cnt : cnt + 1;
            if (dp[ni][nj] < next_cnt) continue;
            dp[ni][nj] = next_cnt;
            pq.push({{-next_cnt, k},
                     {ni,       nj}});
        }
    }
    cout << dp[ended.first][ended.second];
}

int main() {
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios::sync_with_stdio(false);

    cin >> w >> h;
    string s;
    bool flag = false;
    for (int i = 0; i < h; i++) {
        cin >> s;
        for (int j = 0; j < s.size(); j++) {
            map[i][j] = s[j];
            if (s[j] == 'C') {
                if (!flag) {
                    start = {i, j};
                    flag = true;
                } else {
                    ended = {i, j};
                }
            }
        }
    }
    for (int i = 0; i < 101; i++) {
        for (int j = 0; j < 101; j++) {
            dp[i][j] = INF;
        }
    }

    dp[start.first][start.second] = 0;
    for (int k = 0; k < 4; k++) {
        int ni = start.first + di[k];
        int nj = start.second + dj[k];
        if (ni < 0 || ni >= h || nj < 0 || nj >= w) continue;
        if (map[ni][nj] == '*')continue;
        dp[ni][nj] = 0;
        pq.push({{0,  k},
                 {ni, nj}});
    }

    BFS();
}