백준) 6087 - 레이저 통신

처음으로 풀어본 골드4(sloved.ac)문제. 기분이 좋다 ㅎㅎㅎㅎㅎ

느낌상 이건 BFS로 풀어야 할 것 같았다.

 

<문제>

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

6087번: 레이저 통신

<코드>

#include <iostream>
#include <string.h>
#include <queue>

using namespace std;

char map[101][101];
bool check[101][101] = {0, };
int N, H;
int cnt = 0;

void bfs(int x, int y) {
	queue<pair<int, int> > q;
	q.push(make_pair(x, y));
	check[x][y] = true;
	int a, b;
	a = q.front().first;
	b = q.front().second;
	q.pop();
	for(int i = a; i > 0; i--) {
		if(map[i][b] == '*') break;
		if(!check[i][b]){
			check[i][b] = true;
			q.push(make_pair(i, b));
		}
	}
	
	for(int i = a; i <= H; i++) {
		if(map[i][b] == '*') break;
		if(!check[i][b]){
			check[i][b] = true;
			q.push(make_pair(i, b));
		}
	}
	
	for(int i = b; i > 0; i--) {
		if(map[a][i] == '*') break;
		if(!check[a][i]){
			check[a][i] = true;
			q.push(make_pair(a, i));
		}
	}

	for(int i = b; i <= N; i++) {
		if(map[a][i] == '*') break;
		if(!check[a][i]){
			check[a][i] = true;
			q.push(make_pair(a, i));
		}
	}
	
	while(1) {
		int size = q.size();
		for(int i = 0; i < size; i++) {
			a = q.front().first;
			b = q.front().second;
			
			q.pop();
			if(map[a][b] == 'C') {
				cout << cnt << endl;
				return;
			}
			for(int j = a; j > 0; j--) {
				if(map[j][b] == '*') break;
				if(!check[j][b]){
					check[j][b] = true;
					q.push(make_pair(j, b));
				}
			}
	
			for(int j = a; j <= H; j++) {
				if(map[j][b] == '*') break;
				if(!check[j][b]){
					check[j][b] = true;
					q.push(make_pair(j, b));
				}
			}
	
			for(int j = b; j > 0; j--) {
				if(map[a][j] == '*') break;
				if(!check[a][j]){
					check[a][j] = true;
					q.push(make_pair(a, j));
				}
			}
	
			for(int j = b; j <= N; j++) {
				if(map[a][j] == '*') break;
				if(!check[a][j]){
					check[a][j] = true;
					q.push(make_pair(a, j));
				}
			}
		}
		
		cnt++;
	}
	
}

int main(void) {
	memset(map, ' ', sizeof(map));
	int x, y;
	cin >> N >> H;
	for(int i = 1; i <= H; i++) {
		for(int j = 1; j <= N; j++) {
			cin >> map[i][j];
			if(map[i][j] == '*') {
				check[i][j] = true;
			}
			else if(map[i][j] == 'C') {
				x = i;
				y = j;
				
			}
		}
	}
	
	bfs(x, y);
	
	return 0;
}

정말 길고 지저분하다.

이걸 더 깔끔하게 할 방법도 분명히 있을 것 같다.

 

<해석>

예시로 해석을 해보면 다음과 같다.

.	.	.	.	.	.	.
.	.	.	.	.	.	C
.	.	.	.	.	.	*
*	*	*	*	*	.	*
.	.	.	.	*	.	*
.	.	.	.	*	.	*
.	C	.	.	*	.	*
.	.	.	.	.	.	.

map[2][7]의 C에서 부터 시작된다고 가정하자. (사실 시작되는 곳은 어떤 C든 상관 없다.)

이를 기준으로 십자 모양의 모든 '.'들의 좌표를 큐에 넣어주면서 check의 해당 좌표 값을 true로 바꾼다.(기본 세팅)

이때, *를 만나면 break!

 

여기서 check값을 true로 바꾸게 되면, 후에 직진하는건 이미 체크를 한 상태로 굳이 신경 써 줄 필요가 없게 된다.

이 말은 곧 우리는 좌/우로 꺾이는(거울) 상황만 생각하면 된다.

 

이 이후부터는 Queue크기 만큼 for문을 돌려주게 되는데, 기본 세팅과 똑같이 십자 모양의 모든 '.'들의 좌표를 큐에 다시 넣어준다. 하지만, Queue에 들어가는 것은 check가 false인 경우만 들어가게 되는데, 레이저가 원래 방향에서 앞으로 쭉 나가는 경우는 이미 직전에 check를 true로 바꾸어주었기 때문에 Queue에 따로 들어가지 않게 된다.

 

계속 Queue를 빼내면서, 또 다른 C가 있을때 까지 반복.

 

Queue의 size만큼 for문이 돌면, count를 증가시켜준다.

 

 

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

나중에 내가 다시 보면 내 글이 이해되면 좋겠다...ㅠㅠㅠㅠㅠㅠ