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

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

6087번: 레이저 통신

<풀이>

1. 출발 'C' 지점에서 레이저를 발사하여, 각 지점마다 필요한 거울 개수를 세준다.

2. 도착 'C' 지점에 도착하면 사용한 거울 개수를 출력한다.

​

<해법>

1. 필요한 거울 개수를 세는 방법.

=> BFS를 통해 탐색을 진행할 때, 한 칸씩 진행하는 것이 아닌 레이저를 보낼 수 있는 곳 까지 보냅니다. 이렇게 하였을 때 거울 개수를 관리하기 편해집니다.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
struct pos {
    //좌표
    int x, y;
};
 
struct laser {
    //좌표
    pos l;
    //거울 개수
    int cnt;
};
 
int di[] = { -1,0,1,0 };
int dj[] = { 0,1,0,-1 };
 
int W, H;
char map[100][100];
bool visited[100][100];
vector<pos> cPos;
int res;
 
void bfs(laser st) {
    queue<laser> q;
    q.push(st);
    visited[st.l.x][st.l.y] = true;
 
    while (!q.empty()) {
        laser cur = q.front();
        q.pop();
 
        //도착지점에 도착 - 종료
        if (cur.l.x == cPos[1].x && cur.l.y == cPos[1].y) {
            res = cur.cnt;
            return;
        }
 
        //4방향 탐색
        for (int i = 0; i < 4; i++) {
            laser nxt = cur;
 
            //방향으로 갈 수 있는곳 까지 레이저 발사
            while (true) {
                nxt.l.x += di[i];
                nxt.l.y += dj[i];
 
                //레이저가 범위를 넘어섰을 경우, 레이저가 벽을 만났을 경우 - 반복문 탈출
                if (nxt.l.x < 0 || nxt.l.y < 0 || nxt.l.x >= H || nxt.l.y >= W) {
                    break;
                }
                if (map[nxt.l.x][nxt.l.y] == '*') {
                    break;
                }
 
                //이전에 방문하지 않았던 경우 - 거울 개수 + 1
                if (!visited[nxt.l.x][nxt.l.y]) {
                    nxt.cnt = cur.cnt + 1;
                    visited[nxt.l.x][nxt.l.y] = true;
                    q.push(nxt);
                }
            }
        }
    }
}
 
int main() {
 
    //입력
    cin >> W >> H;
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            cin >> map[i][j];
 
            //출발지점, 도착지점 찾기
            if (map[i][j] == 'C') {
                cPos.push_back({ i,j });
            }
        }
    }
 
    //출발지점
    laser st = { {cPos[0].x, cPos[0].y}, -1 };
 
    //출발지점부터 탐색
    bfs(st);
 
    //출력
    cout << res;
 
    return 0;
}

 

BFS와 시뮬레이션에 대해 알아볼 수 있는 문제였습니다.