백준 6087 : 레이저 통신

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

6087번: 레이저 통신

각 칸이 빈 칸이거나 벽이고, 레이저가 두 개 놓여져 있는 지도가 주어졌을 때, 두 레이저를 연결하기 위해 설치해야 하는 거울 개수의 최솟값을 출력하는 문제였습니다. '거울을 설치한다'는 결국 '방향이 바뀐다'로 해석할 수 있으며, 방향이 바뀌는 것은 가중치가 1이고, 방향이 바뀌지 않고 이동하는 것은 가중치가 0으로 생각할 수 있습니다. 그래서 BFS를 통해 문제를 해결했고, 문제 해결 절차는 다음과 같습니다.

 

[1] 입력(column, row 순서의 입력입니다)을 받고 레이저가 있는 위치를 각각 sr, sc, er, ec에 저장합니다. 또한, 벽이라면 2차원 배열에 -1을 저장합니다.

→ 두 레이저 중 아무 곳에서나 BFS를 시작해도 상관없으므로 (strat_r, start_c)에서 end_r, end_c로 BFS를 진행한다고 생각하고 풀었습니다.

 

[2] (sr, sc)에서 BFS 함수를 시작합니다.

 

[3] 일반적인 BFS 함수와 똑같이 동작하지만, 상하좌우 탐색을 하면서 직진으로 이동할 수 있는 곳은 모두 큐에 넣고 방문 처리를 해주고, 거리 정보도 모두 이동을 시작하는 좌표 + 1로 저장합니다.

→ 이렇게 거리 정보를 update 하면 결국 직선(방향을 꺾지 않고 직진하는)의 개수가 최종 도착 좌표에 저장되게 됩니다.

 

[4] 즉, 마지막엔 직선의 개수 - 1을 출력하면 방향을 꺾은 횟수를 출력하는 것과 동일한 결과를 얻게 됩니다.

 

 

[소스코드]

 

#include<cstdio>
#include<queue>
using namespace std;
const int MAX = 100 + 10;
 
char what;
 
// 거리 정보를 저장할 dist 배열
// bfs 시작 레이저 좌표(sr, sc), 도착 레이저 좌표(er, ec)
int n, m, map[MAX][MAX], dist[MAX][MAX], sr = -1, sc, er, ec;
 
const int dr[] = { -1,1,0,0 };
const int dc[] = { 0,0,-1,1 };
 
// (r, c)부터 시작하여 상하좌우를 탐색하며 직진할 수 있으면
// 끝까지 직진하는 bfs를 수행하여 dist 배열에 직선의 개수를
// 저장하고, 도착 좌표의 직선의 개수 - 1을 반환하는 함수
int do_bfs(int r, int c) {
 
    bool check[MAX][MAX] = { 0, };
    queue <pair<int, int>> q;
 
    check[r][c] = true;
    q.push(make_pair(r, c));
 
    while (!q.empty()) {
        int cur_r = q.front().first, cur_c = q.front().second;
        q.pop();
 
        // [3] 상하좌우 탐색
        for (int i = 0; i < 4; i++) {
            int rr = cur_r + dr[i], cc = cur_c + dc[i];
 
            // [3] 배열의 범위를 벗어나거나 벽이 있으면 break
            while (1) {
                if (rr < 0 || rr >= n || cc < 0 || cc >= m) break;
                if (map[rr][cc] == -1) break;
 
                // [3] 아직 방문하지 않은 좌표라면 행과 열의 좌표를
                //     계속 현재 방향으로 한 칸씩 가면서
                //     방문처리 및 큐에 push하고
                if (!check[rr][cc]) {
 
                    // 직진할 수 있는 모든 칸에 대해 거리를
                    // 직진을 시작한 좌표까지의 직선의 개수 + 1로 저장합니다
                    dist[rr][cc] = dist[cur_r][cur_c] + 1;
                    q.push(make_pair(rr, cc));
                    check[rr][cc] = true;
                }
                rr += dr[i];
                cc += dc[i];
            }
        }
    }
    return dist[er][ec] - 1; // [4] 직선의 개수 - 1을 반환합니다
}
 
int main(void) {
 
    scanf("%d%d", &m, &n); // [1]
 
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) {
            scanf(" %c", &what);
            if (what == 'C') {
                if (sr == -1)
                    // [1] 처음에 만나는 레이저를 sr, sc에 저장
                    sr = i, sc = j;
                else
                    // [1] 다음에 만나는 레이저를 er, ec에 저장
                    er = i, ec = j;
            }
            // [1] 벽이라면 map에 -1을 넣어줍니다
            else if (what == '*') map[i][j] = -1;
        }
    printf("%d", do_bfs(sr, sc)); // [2]
    return 0;
}