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

728x90

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

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

문제 링크

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

2151번: 거울 설치

첫째 줄에 집의 크기 N (2 ≤ N ≤ 50)이 주어진다. 다음 N개의 줄에는 N개의 문자로 집에 대한 정보가 주어진다. ‘#’는 문이 설치된 곳으로 항상 두 곳이며, ‘.’은 아무 것도 없는 것으로 빛은

www.acmicpc.net

문제 설명

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

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

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

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

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

입력

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

출력

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

나의 풀이 과정

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

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

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. 그대로 간다
2. 거울을 설치하고 + 진행 방향을 바꾼다 (2가지)
거울이 없는 빈 공간
1. 그대로 간다
벽
1. 못간다
문
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

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

댓글을 작성하려면 로그인해야 합니다.

www.acmicpc.net

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

[BOJ] 2151번 - 거울 설치

백준 2151번 - 거울 설치 시간제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 128 MB 5965 1390 872 23.923% 문제 채영이는 거울을 들여다보는 것을 참 좋아한다. 그래서 집 곳곳에 거울을 설치해두

kangminjun.tistory.com

728x90

'Algorithm' 카테고리의 다른 글

BOJ - 14567번 선수과목 (Prerequisite), 위상 정렬 (Topology sort) 풀이 (C++) (0)	2022.07.29
BOJ - 4485번 녹색 옷 입은 애가 젤다지?, 기본 다익스트라(dijkstra) 문제 (0)	2022.07.25
BOJ - 11909번 배열 탈출 문제, Dijkstra 이용한 풀이 (0)	2022.07.22
BOJ - 1388번 바닥 장식, DFS를 이용한 풀이 (0)	2022.07.22
알고리즘 문제 풀이 정리 (0)	2022.07.22

내 블로그 - 관리자 홈 전환	`Q` `Q`
새 글 쓰기	`W` `W`

글 수정 (권한 있는 경우)	`E` `E`
댓글 영역으로 이동	`C` `C`

이 페이지의 URL 복사	`S` `S`
맨 위로 이동	`T` `T`
티스토리 홈 이동	`H` `H`
단축키 안내	`Shift` + `/` `⇧` + `/`

코딩 일지

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

'Algorithm' 카테고리의 다른 글

댓글

티스토리툴바

개인정보

단축키

내 블로그

블로그 게시글

모든 영역

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

'Algorithm' 카테고리의 다른 글

관련글

댓글

티스토리툴바

개인정보

단축키

내 블로그

블로그 게시글

모든 영역