BOJ - 2151번 거울 설치 문제, BFS 풀이

이번에는 골드 3 난이도의 백준 2151번 문제 풀이한 과정을 정리해보려 합니다.

 

이번 문제는 그래프를 탐색과 관련된 문제여서 쉽게 풀 수 있을 줄 알았는데, 거의 10번 정도 틀리고 질문의 다른 테스트 케이스들과 정리 글들을 참고해서 겨우 풀었던 것 같습니다.

쉽지않다

 

문제 링크

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

2151번: 거울 설치

---

문제 설명

채영이는 거울을 들여다보는 것을 참 좋아한다. 그래서 집 곳곳에 거울을 설치해두고 집 안을 돌아다닐 때마다 거울을 보곤 한다.

 

채영이는 새 해를 맞이하여 이사를 하게 되었는데, 거울을 좋아하는 그녀의 성격 때문에 새 집에도 거울을 매달만한 위치가 여러 곳 있다. 또한 채영이네 새 집에는 문이 두 개 있는데, 채영이는 거울을 잘 설치하여 장난을 치고 싶어졌다. 즉, 한쪽 문에서 다른 쪽 문을 볼 수 있도록 거울을 설치하고 싶어졌다.

 

채영이네 집에 대한 정보가 주어졌을 때, 한 쪽 문에서 다른 쪽 문을 볼 수 있도록 하기 위해 설치해야 하는 거울의 최소 개수를 구하는 프로그램을 작성하시오.

 

거울을 설치할 때에는 45도 기울어진 대각선 방향으로 설치해야 한다. 또한 모든 거울은 양면 거울이기 때문에 양 쪽 모두에서 반사가 일어날 수 있다. 채영이는 거울을 매우 많이 가지고 있어서 거울이 부족한 경우는 없다고 하자.

거울을 어떻게 설치해도 한 쪽 문에서 다른 쪽 문을 볼 수 없는 경우는 주어지지 않는다.

 

입력

첫째 줄에 집의 크기 N (2 ≤ N ≤ 50)이 주어진다. 다음 N개의 줄에는 N개의 문자로 집에 대한 정보가 주어진다. ‘#’는 문이 설치된 곳으로 항상 두 곳이며, ‘.’은 아무것도 없는 것으로 빛은 이곳을 통과한다. ‘!’은 거울을 설치할 수 있는 위치를 나타내고, ‘*’은 빛이 통과할 수 없는 벽을 나타낸다.

 

출력

첫째 줄에 설치해야 할 거울의 최소 개수를 출력한다.

---

나의 풀이 과정

 

우선 처음에는 다익스트라를 이용해서 풀이했는데, 배열에 각 칸에서 현재까지 최소 거울 설치 수에 대한 정보를 저장하면서 이 값을 기준으로 그래프를 탐색하며 각 칸으로 가는 최소 거울 설치 수를 갱신하는 방식으로 구하도록 구현했습니다.

예시 1

하지만, 이렇게 구현하는 경우 결국 도착점에 도착했을 때 이 최소 거울의 개수가 의미가 있는 것이기 때문에 다음 문으로 도착하지 못하는 경우 때문에, 중간 과정에서 탐색이 중단돼어 올바른 답을 구하지 못하는 경우가 발생해 이 풀이는 실패했습니다. 

 

e.g. 예시 1에서 (dp는 각 칸에서의 현재까지 최소 거울 수를 저장하는 배열)

(0, 0) -> 아래 경로 탐색 (1, 0) -> 우측 경로 탐색 (1, 1) => dp[1][1] = 1 (방향 우측 보는 중)

(0, 0) -> 우측 경로 탐색 (0, 1) -> 아래 경로 탐색 (1, 1) => dp[1][1] = 1 (방향 아래 보는 중)

 

위 경우 앞에서 이미 dp[1][1]이 1로 갱신되어 있어서 두 번째 탐색이 무시됩니다. (이걸 해결해주니 또 다른 문제가 발생해서 다익스트라는 포기했습니다..)

 

글을 쓰면서 생각해보니 다익스트라로 풀려면, "각 칸 + 현재 진행 방향"을 기준으로 최소 거울 개수를 기준으로 dynamic programming 기법을 적용해야 될 것 같습니다.

 

😭 dp[1][1][방향] 이런 식으로 각 위치에서 최소 거울 수를 갱신하면 문제를 해결할 수 있지 않았을까 싶습니다. 😭

 

어쨌든 여러 테스트 케이스를 살펴보다 결국에는 BFS로 그래프를 탐색하면서 다음 문에 도착한 case에 대해 최소 거울 개수를 갱신하는 방식으로 모든 발생 가능한 경로를 찾으면 풀 수 있을 것 같다고 생각이 들어 BFS를 이용해 풀이하게 되었습니다.

---

저는 다음과 같은 규칙을 기준으로 문제를 풀이하려고 했습니다!

1. 거울을 설치할 수 있는 위치에서 택할 수 있는 옵션
   1. 그대로 간다
   2. 거울을 설치하고 + 진행 방향을 바꾼다 (2가지)
2. 거울이 없는 빈 공간
   1. 그대로 간다
3. 벽
   1. 못간다
4. 문
   1. 4개의 방향으로 진행 가능 (물론 벽이거나 범위를 벗어나면 못 간다)

거울은 둘 중 하나와 같이 설치됩니다.

거울을 설치하게 되면, 진행 방향과 수직인 방향으로 이동 가능하다고 생각했고 (거울은 진행 방향에 맞춰 알아서 설치한다고 생각했습니다.) 설치하지 않는 경우에는 빈 공간과 같이 취급할 수 있다고 판단했습니다.

 

---

참고한 Test Case 들 👍🏻👍🏻

input #1
3
#!.
!!.
*#.

output #1
1

input #2
3
...
*!#
#!!

output #2
1

input #3
2
!#
!#

output #3
0

input #4
30
#!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!#

output #4
1

reference:
https://www.acmicpc.net/board/view/14919

 

---

소스 코드 👍🏻👍🏻

/*
	Date: 2022/07/20
	Brief:
	BFS
	Reference:
*/
#include <iostream>
#include <string>
#include <queue>

#define MAX 51
#define INF 2501
using namespace std;
// 집의 정보를 저장하는 배열
string houseInfo[MAX];
// 최소 거울의 개수를 저장하는 변수
int res = INF;

int n;
// 0(상), 1(하), 2(좌), 3(우)
int dx[] = { -1, 1, 0, 0 };
int dy[] = { 0, 0, -1, 1 };

// 중복 방문을 막기 위해 위치, 거울 수, 방향을 기준으로 방문 여부를 판단하는 visited 배열 사용
bool visited[MAX][MAX][2501][4] = {false,};

vector<pair<int, int>> doorSite;

bool inRange(int x, int y) {
	return (0 <= x && x < n && 0 <= y && y < n);
}

void BFS(int x, int y) {
	// pair<pair<거울 수, 방향>, pair<x, y>>
	queue<pair<pair<int, int>, pair<int, int>>> q;

	// 첫 문의 4방향을 queue에 넣어준다.
	for (int i = 0; i < 4; i++) {
		int next_x = x + dx[i];
		int next_y = y + dy[i];

		int next_g = 0;
		int next_d = i;

		if (!inRange(next_x, next_y))
			continue;
		// 다음 칸이 벽인 경우 스킵
		if (houseInfo[next_x][next_y] == '*')
			continue;
		visited[next_x][next_y][next_g][next_d] = true;
		q.push({ {next_g, next_d}, {next_x, next_y} });
	}

	while (!q.empty()) {
		int cur_x = q.front().second.first;
		int cur_y = q.front().second.second;

		int cur_g = q.front().first.first;
		int cur_d = q.front().first.second;
		q.pop();

		if (cur_g > res)
			continue;

		//cout << cur_x << " " << cur_y << " " << cur_g << " " << cur_d << endl;
		// 현재 칸이 문인 경우
		if (houseInfo[cur_x][cur_y] == '#' && cur_x == doorSite[1].first && cur_y == doorSite[1].second) {
			// 문에 도착한 경우 갱신 가능한지 판단한다.
			res = (res > cur_g) ? cur_g : res;
			continue;
		}
		else if (houseInfo[cur_x][cur_y] == '.') {
			// 빈 공간인 경우 이전 방향 그대로 진행한다.
			int next_x = cur_x + dx[cur_d];
			int next_y = cur_y + dy[cur_d];

			int next_g = cur_g;
			int next_d = cur_d;

			if (!inRange(next_x, next_y))
				continue;
			// 다음 칸이 벽인 경우 스킵 or 이미 방문한 경우 스킵
			if (houseInfo[next_x][next_y] == '*' || visited[next_x][next_y][next_g][next_d])
				continue;
			visited[next_x][next_y][next_g][next_d] = true;
			q.push({ {next_g, next_d}, {next_x, next_y} });
		}
		else {
			// 거울인 경우 세 개의 방향으로 틀어진다. (현재 진행 방향에 수직 or 그대로 간다.)
			for (int i = 0; i < 4; i++) {
				if (cur_d == 0 && i == 1)
					continue;
				if (cur_d == 1 && i == 0)
					continue;
				if (cur_d == 2 && i == 3)
					continue;
				if (cur_d == 3 && i == 2)
					continue;
				

				int next_x = cur_x + dx[i];
				int next_y = cur_y + dy[i];

				int next_g = cur_g;
				int next_d = i;

				//cout << "거울: " << next_x << " " << next_y << " " << next_g << " " << next_d << endl;

				if (!inRange(next_x, next_y))
					continue;
				// 다음 칸이 벽인 경우 스킵
				if (houseInfo[next_x][next_y] == '*')
					continue;

				// 진행 방향이 바뀌는 경우 거울 수를 추가한다. (거울을 설치하는 경우)
				if (next_d != cur_d)
					next_g++;

				// 이미 방문한 경우 스킵한다.
				if (visited[next_x][next_y][next_g][next_d])
					continue;

				visited[next_x][next_y][next_g][next_d] = true;
				//cout << "거울" << next_x << " " << next_y << " " << next_g << " " << next_d << endl;
				q.push({ {next_g, next_d}, {next_x, next_y} });
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> houseInfo[i];
	}
	int i, j;

	for (i = 0; i < n; i++) {
		for (j = 0; j < n; j++) {
			if (houseInfo[i][j] == '#') {
				doorSite.push_back({ i, j });
			}
		}
	}
	BFS(doorSite[0].first, doorSite[0].second);

	cout << res << "\n";

	return 0;
}

/*
idea

거울을 설치할 수 있는 위치에서 택할 수 있는 옵션
1. 그대로 간다
2. 거울을 설치하고 + 진행 방향을 바꾼다 (2가지)

거울이 없는 빈 공간
1. 그대로 간다

벽
1. 못간다

문
1. 4개의 방향으로 진행 가능
*/

---

References

https://www.acmicpc.net/board/view/14919

글 읽기 - 문제 조건 & 데이터를 추가해 주세요.

https://kangminjun.tistory.com/entry/BOJ-2151%EB%B2%88-%EA%B1%B0%EC%9A%B8-%EC%84%A4%EC%B9%98

[BOJ] 2151번 - 거울 설치