[백준 6087] 레이저 통신

문제 링크 => 6087번: 레이저 통신 (acmicpc.net)

6087번: 레이저 통신

 

BFS 문제이다.

 

사실 이런 유형의 문제는 몇번 풀어봤지만 아직도 부등호를 정확하게 어떻게 잡아야 할지에 대해서는 

여러번 디버깅을 통해서 찾고는 한다.

 

int 타입의 check 배열을 선언함으로써 해당 위치에 대한 거울을 놓을 수 있는 최소 갯수를 판단하기

위한 용도가 필요하다.

 

또한 이전에 어떠한 거울로 인해서 가르키는 방향에 대한 정보도 필요하다.

 

시작 지점부터 끝 지점까지 BFS 를 하면서 임의의 지점 (cx, cy) 에 대하여 다음 지점 (nx, ny)으로

이동할 때 거울의 갯수가 증가할지 안할지에 대한 여부와 그 갯수로 인하여 다음 지점에서 똑같은

operation 을 반복할지에 대한 점검이 필요하다.

 

 

요약하자면

 

1. 시작 지점에서는 어느 방향으로 가든 거울의 갯수가 0이다.

 

2. 끝 지점에 도착할 경우 될 수 있는 모든 거울의 갯수중에 최소를 골라내면 된다.

 

3. 시작 지점도 끝 지점도 아닌 경우 )

    - 현재 위치(cx, cy)에서 다음 위치(nx, ny)로 이동하기 위한 거울의 총 갯수가 해당 지점에서의

      거울을 놓을 수 있는 최소 갯수(check[nx][ny])를 비교한다. 

    - 비교하여 작거나 같을 경우에 다음 지점으로 이동하도록 한다.

 

 

Solution Code

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string>
#include <iostream>
#include <algorithm>
#include <queue>

#define INF 1000000000

using namespace std;

int W, H;
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
char Map[101][101];
int check[101][101];

struct mapInfo {
	int x, y, direction, mirror;
	mapInfo(int x, int y, int direction, int mirror) {
		this->x = x;
		this->y = y;
		this->direction = direction;
		this->mirror = mirror;
	}
};

void initialize() 
{
	for (int i = 0; i < H; i++)
		for (int j = 0; j < W; j++)
			check[i][j] = INF;
}

int solution(int sX, int sY, int eX, int eY)
{
	queue<mapInfo> Q;
	int curX, curY, direction, mirror;
	int nextX, nextY, result;

	initialize();
	Q.push({ sX,sY, -1, 0 });
	result = INF, check[sX][sY] = 0;
	while (!Q.empty()) {
		curX = Q.front().x, curY = Q.front().y;
		direction = Q.front().direction, mirror = Q.front().mirror;
		Q.pop();

		for (int i = 0; i < 4; i++) {
			nextX = curX + dx[i], nextY = curY + dy[i];
			if (nextX >= 0 && nextX < H && nextY >= 0 && nextY < W 
				&& Map[nextX][nextY] != '*') {
				if (nextX == eX && nextY == eY) 
					result = min(result, mirror + (direction == i ? 0 : 1));
				else {
					if (direction == -1) {
						Q.push({ nextX,nextY,i,0 });
						check[nextX][nextY] = 0;
					}
					else {
						if (mirror + (direction == i ? 0 : 1) <= check[nextX][nextY]) {
							Q.push({ nextX,nextY,i,mirror + (direction == i ? 0 : 1) });
							check[nextX][nextY] = mirror + (direction == i ? 0 : 1);
						}
					}
				}
			}
		}
	}

	return result;
}

int main(void) 
{
	int sX, sY, eX, eY;

	cin >> W >> H;
	sX = -1;
	for (int i = 0; i < H; i++) {
		string line;
		cin >> line;
		for (int j = 0; j < W; j++) {
			Map[i][j] = line[j];
			if (Map[i][j] == 'C') {
				if (sX == -1) sX = i, sY = j;
				else eX = i, eY = j;
			}
		}
	}
	
	cout << min(solution(sX, sY, eX, eY), solution(eX, eY, sX, sY));

	return 0;
}