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

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

6087번: 레이저 통신

문제

크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다.

'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 설치해야 하는 거울 개수의 최솟값을 구하는 프로그램을 작성하시오. 레이저로 통신한다는 것은 두 칸을 레이저로 연결할 수 있음을 의미한다.

레이저는 C에서만 발사할 수 있고, 빈 칸에 거울('/', '\')을 설치해서 방향을 90도 회전시킬 수 있다. 

아래 그림은 H = 8, W = 7인 경우이고, 빈 칸은 '.', 벽은 '*'로 나타냈다. 왼쪽은 초기 상태, 오른쪽은 최소 개수의 거울을 사용해서 두 'C'를 연결한 것이다.

입력

첫째 줄에 W와 H가 주어진다. (1 ≤ W, H ≤ 100)

둘째 줄부터 H개의 줄에 지도가 주어진다. 지도의 각 문자가 의미하는 것은 다음과 같다.

• .: 빈 칸
• *: 벽
• C: 레이저로 연결해야 하는 칸

'C'는 항상 두 개이고, 레이저로 연결할 수 있는 입력만 주어진다.

출력

첫째 줄에 C를 연결하기 위해 설치해야 하는 거울 개수의 최솟값을 출력한다.

 

시작지점에서 목적지까지 가는 데에 있어 방향 전환이 가장 적은 것을 저장하고 마지막에 출력하는 문제이다.

<이런 유형의 문제들을 풀 때 기억해야할 것이 있어 작성한다.>

대부분의 너비 우선 탐색 기법을 사용하는 그래프 탐색 문제는 visited배열을 통해 방문여부를 검사한 후 아직 방문을 하지 않았으면 false를 true로 바꿔 방문처리를 한다. 그리고 큐에 넣어 이어나가는 방식인데 위 유형의 문제같은 경우는 방문처리를 하는 방식이 아닌 최소값을 최신화 해주는 방식으로 구현해주어야한다. 그 이유는 false/true로 방문처리만 해주는 경우에는 후에 올 수 있는 값들을 비교할 수 없기 때문이다. 그래서 맨 처음에 visited배열을 INF값으로 설정한 후 BFS를 진행하면서 최소값을 갱신할 수 있으면 갱신해주는 방법으로 구현해주어야 한다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

struct node {
	int x;
	int y;
	int Direct;
};

int row, col, purpose_x, purpose_y, start_x, start_y;
const node dir[4] = { {1,0,1}, {-1,0,2}, {0,1,3}, {0,-1,4} };

char adj[101][101];
int visited[101][101];

queue<pair<pair<int, int>,pair<int,int>>> q;

void input() {
	bool first = false;
	cin >> row >> col;
	for (int i = 0; i < col; i++) {
		for (int j = 0; j < row; j++) {
			cin >> adj[i][j];
			if (adj[i][j] == 'C') {
				if (first == false) {
					first = true;
					start_x = i;
					start_y = j;
				}
				else {
					purpose_x = i;
					purpose_y = j;
				}
			}
			visited[i][j] = 987654321;		
		}
	}
}

int BFS(int new_x, int new_y) {
	int nextX, nextY, nextDir;
	for (int i = 0; i < 4; i++) {
		q.push(make_pair(make_pair(new_x, new_y), make_pair(dir[i].Direct, 0)));
	}
	visited[new_x][new_y] = 0;
	while (!q.empty()) {
		int cur_x = q.front().first.first;
		int cur_y = q.front().first.second;
		int cur_dir = q.front().second.first;
		int cur_cnt = q.front().second.second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			nextX = cur_x + dir[i].x;
			nextY = cur_y + dir[i].y;
			nextDir = dir[i].Direct;
			int save_cnt = cur_cnt;

			if (nextX < 0 || nextY < 0 || nextX >= col || nextY >= row) continue;
			if (adj[nextX][nextY] == '*') continue;

			if (cur_dir != nextDir) save_cnt += 1;
			if (visited[nextX][nextY] >= save_cnt) {
				q.push(make_pair(make_pair(nextX, nextY), make_pair(nextDir, save_cnt)));
				visited[nextX][nextY] = save_cnt;
			}
		}
	}
	return visited[purpose_x][purpose_y];
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	input();
	cout << BFS(start_x, start_y) << endl;

	return 0;
}