[백준 2151] 거울 설치

문제 링크 => 2151번: 거울 설치 (acmicpc.net)

2151번: 거울 설치

---

BFS 문제이며 문제를 접근한 알고리즘은 다음과 같다.

 

1. 시작 지점의 방향은 -1로 설정해두고 그 이후로는 0~3(상하좌우) 가 되도록 구현하였다.

=> 이때, class Light 를 활용하여 위치(x, y), 방향(direction)을 설정하도록 하였고, 

queue<pair<Light,int>> q; 에서 int는 거울을 배치한 갯수를 담도록 설정하였다.

또한 시작지점의 방문처리도 해주었다. (1로 설정하였는데 배치한 갯수+1로 보면 된다.)

 

2. 시작 지점에서는 상하좌우로 이동하도록 하고 그 이후로는 direction 에 의존하여 이동하도록 하였다.

 

3. 시작 지점인 경우 )

(1) 다음 구역에서 '.' 을 발견한 경우 => Queue에 next 좌표와 방향, cnt 값을 그대로 push

(2) 다음 구역에서 '!'(거울) 을 발견한 경우 => 위아래 / 좌우 에 따라서 다음과 같이 Queue에 push한다.

예를들어서 위아래인 경우 거울은 좌우로 이동하도록 하므로 총 3가지를 push 해야 한다.

방향 그대로 push할 경우 cnt 그대로, 좌우로 push할 경우 cnt+1 을 해줘야 한다.

즉, 오른쪽 방향으로 이동할 경우에 거울을 발견한 경우 오른쪽방향으로 그대로 push할 때는 거울을 배치하지 않으므로 cnt 그대로, 위아래방향으로 push할 때는 거울을 배치하므로 cnt+1을 해줘서 push한다.

(3) 다음 구역에서의 방문처리를 해준다. (이때, 방문처리는 cnt+1으로 설정해둠) 

 

4. 그 외의 지점인 경우 => direction에 의존하여 3번과 동일하게 구현하였으나 방문된 경우에 접근하는 경우를 다음과 같이 처리하였다.

 

(1) 빛이 그대로 통과할 수 있는 '.' 구역은 상관없이 Queue에 push

(2) 거울을 발견할 경우 현재까지 거울을 배치한 갯수가 방문되어 있는 거울의 배치 수보다 작은 경우 Queue에 push하고 방문처리를 현재 cnt+1 값으로 수정해준다.

(3) 그외에 도착지점을 발견할 경우에 result=min(result, cnt) 를 해줘서 가장 배치를 적게한 수를 저장하도록 한다.

 

---

구현에 있어서 놓쳤던 점

 

92% 에서 실패가 떠서 질문게시판에 있는 반례들을 돌리다가 다음과 같은 반례를 발견하였다.

 

3
#!.
!!.
*#.

 

start 위치를 (0, 0) 이라고 둘 경우 : (0, 0) => (0, 1) 거울 배치 => (1, 1) => (2, 1) , 총 1번

start 위치를 (2, 1) 이라고 둘 경우 : (2, 1) => (1, 1) 거울 배치 => (1, 0) 거울 배치 => (0, 0) , 총 2번

 

이때 start 위치와 end 위치가 한개가 아닌 2개이며 이를 캐치하지 못해서 통과하지 못하였다.

 

풀이 code

 

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <time.h>
#define INF 100000000
#define endl '\n'

using namespace std;

char arr[50][50];
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };
int visited[50][50];
int n, firstX = -1, firstY, endX, endY;
int result = INF;

class Light {
public:
	int x, y, direction;
	Light(int x, int y, int direction) {
		this->x = x;
		this->y = y;
		this->direction = direction;
	}
};

void input() {
	cin >> n;
	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
			if (arr[i][j] == '#') {
				if (firstX == -1) firstX = i, firstY = j;
				else endX = i, endY = j;
			}
		}
	}
}

void solve(int firstX,int firstY,int endX,int endY) {
	queue<pair<Light,int>> q;
	q.push({ { firstX,firstY,-1 },0 });
	visited[firstX][firstY] = 1;

	while (!q.empty()) {
		int x = q.front().first.x;
		int y = q.front().first.y;
		int direction = q.front().first.direction;
		int cnt = q.front().second;
		q.pop();

		if (direction == -1) {
			for (int i = 0; i < 4; i++) {
				int nextX = x + dx[i];
				int nextY = y + dy[i];
				
				if (nextX >= 0 && nextX < n && nextY >= 0 && nextY < n) {
					if (arr[nextX][nextY] == '.') {
						q.push({ {nextX,nextY,i},cnt });
					}
					else if (arr[nextX][nextY] == '!') {
						if (i == 0 || i == 1) {
							q.push({ {nextX,nextY,i},cnt });
							q.push({ {nextX,nextY,2},cnt + 1 });
							q.push({ {nextX,nextY,3},cnt + 1 });
						}
						else {
							q.push({ {nextX,nextY,i},cnt });
							q.push({ {nextX,nextY,0},cnt + 1 });
							q.push({ {nextX,nextY,1},cnt + 1 });
						}
					}
					else if (nextX == endX && nextY == endY) {
						result = min(result, cnt);
					}
					visited[nextX][nextY] = cnt + 1;
				}
			}
		}
		else {
			int nextX = x + dx[direction];
			int nextY = y + dy[direction];
			
			if (nextX >= 0 && nextX < n && nextY >= 0 && nextY < n) {
				if (!visited[nextX][nextY]) {
					if (arr[nextX][nextY] == '.') {
						q.push({ {nextX,nextY,direction},cnt });
					}
					else if (arr[nextX][nextY] == '!') {
						if (direction == 0 || direction == 1) {
							q.push({ {nextX,nextY,direction},cnt });
							q.push({ {nextX,nextY,2},cnt + 1 });
							q.push({ {nextX,nextY,3},cnt + 1 });
						}
						else {
							q.push({ {nextX,nextY,direction},cnt });
							q.push({ {nextX,nextY,0},cnt + 1 });
							q.push({ {nextX,nextY,1},cnt + 1 });
						}
					}
					else if (nextX == endX && nextY == endY) {
						result = min(result, cnt);
					}
					visited[nextX][nextY] = cnt + 1;
				}
				else {
					if (arr[nextX][nextY] == '.') {
						q.push({ {nextX,nextY,direction},cnt });
						visited[nextX][nextY] = cnt + 1;
					}
					else {
						if (cnt < visited[nextX][nextY] - 1) {
							if (arr[nextX][nextY] == '!') {
								if (direction == 0 || direction == 1) {
									q.push({ {nextX,nextY,direction},cnt });
									q.push({ {nextX,nextY,2},cnt + 1 });
									q.push({ {nextX,nextY,3},cnt + 1 });
								}
								else {
									q.push({ {nextX,nextY,direction},cnt });
									q.push({ {nextX,nextY,0},cnt + 1 });
									q.push({ {nextX,nextY,1},cnt + 1 });
								}
							}
							else if (nextX == endX && nextY == endY) {
								result = min(result, cnt);
							}
							visited[nextX][nextY] = cnt + 1;
						}
					}
				}
			}
		}
	}
	return;
}

void init() {
	for (int i = 0; i < 50; i++) {
		for (int j = 0; j < 50; j++) {
			visited[i][j] = 0;
		}
	}
}

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

	input();
	solve(firstX,firstY,endX,endY);
	init();
	solve(endX, endY, firstX, firstY);
	cout << result;

	return 0;
}