백준 6087번 레이저통신 (C++)

문제 링크 : https://www.acmicpc.net/problem/6087

6087번: 레이저 통신

이 문제는 유의 사항이 다음과 같다.

 

(1) 통신이 가능한 케이스만 주어진다.

(2) 최단 거리가 아닌, 최소로 거울을 활용하는 횟수를 구해야한다.

(3) 거울을 사용한다는 뜻은 방향을 바꾼다는 의미이다

 

문제 풀이는 다음과 같다.

 

1. 필요한 변수들을 선언하고 값을 입력 받는다. 코드는 하기와 같으며, 설명은 아래를 참고하자.

void input() {
    int temp = 0;
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j <= w; j++) {
            cin >> v[i][j];
            if (v[i][j] == 'C' && temp == 0) {
                s1 = i, s2 = j; // 1. 통신 위치 저장 1
                temp++;
            }
            else if (v[i][j] == 'C' && temp > 0) d1 = i, d2 = j; // 2. 통신 위치 저장 2
        }
    }
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j <= w; j++) map[i][j] = MAX; // 3. 누적 거울 사용 횟수
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> w >> h;
    v.resize(h + 1, vector<char>(w + 1));
    map.resize(h + 1, vector<int>(w + 1));
    input();
    bfs(); // 4
    cout << map[d1][d2] << "\n";
    return 0;
}

(1) ~ (2) 통신 위치를 각각 저장한다.

(3) map이라는 배열에 누적 거울 사용 횟수를 저장할 것이다. 이때 초기값으로 MAX(=1e9로 define됨)을 활용한다.

(4) bfs를 진행한다. 이 bfs를 통해 모든 경로를 지나 가장 최소로 거울을 사용하는 값들이 map에 저장될 것이다.

(5) bfs가 종료된 후 목적지에 저장된 최소 거울 활용 횟수를 출력한다.

 

2. 다음은 BFS의 코드 내부이다.

typedef pair<pair<int,int>, pair<int, int>> r;

void bfs() {
    queue<r> q;
    q.push({ {-1,-1},{s1,s2} }); // 1
    ch[s1][s2] = true;
    map[s1][s2] = -1; // 2
    while (!q.empty()) {
        exm = q.front().first.first;
        m = q.front().first.second;
        y = q.front().second.first;
        x = q.front().second.second;
        q.pop();
        for (int i = 0; i < 4; i++) { // 3
            ny = y + my[i];
            nx = x + mx[i];
            nm = m;
            if (i != exm) nm++; // 4
            if (ny > 0 && ny <= h && nx > 0 && nx <= w && v[ny][nx]!='*') { // 5
                if (!ch[ny][nx] || map[ny][nx] >= nm) { // 6
                    ch[ny][nx] = true; // 7
                    map[ny][nx] = nm; // 8
                    q.push({ {i,nm},{ny,nx} });
                }
            }
        }
    }
}

(1) 큐에 현재 방향, 누적 거울 사용 횟수, 위치를 저장한다.

이때 최초로 4방위로 움직일때 누적 거울 횟수는 0이어야 하므로, 최초 누적 거울 사용 횟수는 -1로 저장한다.

(2) 최초 시작지점의 map은 -1로 저장한다.

(3) 큐의 front()값을 기준으로 4방위로 for문을 진행한다.

(4) 움직인 방향을 업데이트 해주고, 누적 거울 사용 횟수의 경우 이전 방향(exm)과 다를경우 그 값을 +1 해준다

(5) 큐에 넣을때 첫 번째 조건은 해당 범위가 가능 범위를 초과하지 않았는가, 그리고 해당 위치가 '*'이 아닌가 이다.

(6) 만약 해당 위치를 아직 방문하지 않았거나, 혹은 해당 위치의 누적 거울 사용 횟수보다 현재 거울 사용 횟수가 그 이하일 경우, 

방문 표시를 해주고 map의 값을 업데이트 해주며, 마지막으로 큐에 업데이트 된 값들을 저장해준다.

 

3. BFS를 종료하고 목적지의 map 값을 출력해준다.

 

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#define MAX 1e9
using namespace std;

int w, h, s1, s2, d1, d2, exm, m, y, x, exnm, nm, ny, nx, my[] = { 1,0,-1,0 }, mx[] = { 0,1,0,-1 };
vector<vector<char>> v;
vector<vector<int>> map;
typedef pair<pair<int,int>, pair<int, int>> r;
bool ch[101][101];

void bfs() {
    queue<r> q;
    q.push({ {-1,-1},{s1,s2} });
    ch[s1][s2] = true;
    map[s1][s2] = -1;
    while (!q.empty()) {
        exm = q.front().first.first;
        m = q.front().first.second;
        y = q.front().second.first;
        x = q.front().second.second;
        q.pop();
        for (int i = 0; i < 4; i++) {
            ny = y + my[i];
            nx = x + mx[i];
            nm = m;
            if (i != exm) nm++;
            if (ny > 0 && ny <= h && nx > 0 && nx <= w && v[ny][nx]!='*') {
                if (!ch[ny][nx] || map[ny][nx] >= nm) {
                    ch[ny][nx] = true;
                    map[ny][nx] = nm;
                    q.push({ {i,nm},{ny,nx} });
                }
            }
        }
    }
}

void input() {
    int temp = 0;
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j <= w; j++) {
            cin >> v[i][j];
            if (v[i][j] == 'C' && temp == 0) {
                s1 = i, s2 = j;
                temp++;
            }
            else if (v[i][j] == 'C' && temp > 0) d1 = i, d2 = j;
        }
    }
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j <= w; j++) map[i][j] = MAX;
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> w >> h;
    v.resize(h + 1, vector<char>(w + 1));
    map.resize(h + 1, vector<int>(w + 1));
    input();
    bfs();
    cout << map[d1][d2] << "\n";
    return 0;
}

이 코드는 28ms가 소비되었다.