[boj] 백준 6087 레이저 통신 (c++) - BFS

[문제]

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

6087번: 레이저 통신

 

[풀이]

조건이 추가된 BFS 문제.

 

설치해야 할 거울 개수의 최솟값을 구하기 위해 visited 배열에 해당 좌표까지 도달하는데 사용된 거울의 최소 개수를 저장한다.

 

고려해야 하는 것은 크게 2가지이다.

1. 진행 방향과 그 다음 이동할 방향 -> 거울을 이용해 방향이 꺾이는 경우

이동하고자 하는 방향과 현재 진행 방향이 다르면 거울을 설치할 수 있다.

2. 거울의 개수

해당 좌표에서의 거울의 개수보다 현재까지 설치된 거울의 개수가 적으면 갱신해주도록 함으로써 visited 배열에 최소 거울 개수 정보를 저장한다.

 

 

[코드]

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#include <cmath>
#include <tuple>
#define INF 987654321

using namespace std;

int h, w;
char map[101][101];
int visited[101][101];
pair<int, int> s, e;
//동 서 남 북
int dr[4] = {0, 0 ,1, -1};
int dc[4] = {1, -1, 0, 0};

int bfs(){
    queue<pair<pair<int, int>, pair<int, int>>> q; //r, c, 거울 갯수, 방향
    int r = s.first;
    int c = s.second;
    visited[r][c] = 0;

    for(int i=0; i<4; i++){
        q.push({{r, c}, {0, i}});
    }
    
    while(!q.empty()){
        int r = q.front().first.first;
        int c = q.front().first.second;
        int mirror = q.front().second.first;
        int dir = q.front().second.second;
        q.pop();

        for(int i=0; i<4; i++){
            int nr = r + dr[i];
            int nc = c + dc[i];

            int temp = mirror;

            if(nr < 0 || nc < 0 || nr >= h || nc >= w || map[nr][nc]=='*') continue;

            //이동하고자 하는 방향이 다르면 거울 설치가 필요
            if(dir!=i){
                temp++;
            }
            if(visited[nr][nc] >= temp){
                visited[nr][nc] = temp;
                q.push({{nr, nc},{temp, i}});
            }
        }
    }

    return visited[e.first][e.second];
}

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

    cin >> w >> h;
    int temp = 0;
    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            cin >> map[i][j]; //. 빈 칸, * 벽, C 레이저로 연결해야 하는 칸
            if(map[i][j]=='C'){
                if(temp==0){
                    s.first = i;
                    s.second = j;
                    temp++;
                }
                else{
                    e.first = i;
                    e.second = j;
                }
            }
            visited[i][j] = INF;
        }
    }

    cout << bfs();


}