문제
채영이는 거울을 들여다보는 것을 참 좋아한다. 그래서 집 곳곳에 거울을 설치해두고 집 안을 돌아다닐 때마다 거울을 보곤 한다.
채영이는 새 해를 맞이하여 이사를 하게 되었는데, 거울을 좋아하는 그녀의 성격 때문에 새 집에도 거울을 매달만한 위치가 여러 곳 있다. 또한 채영이네 새 집에는 문이 두 개 있는데, 채영이는 거울을 잘 설치하여 장난을 치고 싶어졌다. 즉, 한 쪽 문에서 다른 쪽 문을 볼 수 있도록 거울을 설치하고 싶어졌다.
채영이네 집에 대한 정보가 주어졌을 때, 한 쪽 문에서 다른 쪽 문을 볼 수 있도록 하기 위해 설치해야 하는 거울의 최소 개수를 구하는 프로그램을 작성하시오.
거울을 설치할 때에는 45도 기울어진 대각선 방향으로 설치해야 한다. 또한 모든 거울은 양면 거울이기 때문에 양 쪽 모두에서 반사가 일어날 수 있다. 채영이는 거울을 매우 많이 가지고 있어서 거울이 부족한 경우는 없다고 하자.
거울을 어떻게 설치해도 한 쪽 문에서 다른 쪽 문을 볼 수 없는 경우는 주어지지 않는다.
입력
첫째 줄에 집의 크기 N (2 <= N <= 50)이 주어진다. 다음 N개의 줄에는 N개의 문자로 집에 대한 정보가 주어진다. ‘#’는 문이 설치된 곳으로 항상 두 곳이며, ‘.’은 아무 것도 없는 것으로 빛은 이 곳을 통과한다. ‘!’은 거울을 설치할 수 있는 위치를 나타내고, ‘*’은 빛이 통과할 수 없는 벽을 나타낸다.
출력
첫째 줄에 설치해야 할 거울의 최소 개수를 출력한다.
풀이
거울을 설치할 수 있는 칸에 도달했을 때, 앞으로 직진할지, 좌로 꺾을지, 우로 꺾을지를 선택하면서 최소 거울 수를 갱신하는 문제다. 얼핏 보면 단순 BFS 같지만, 거리를 배열에 저장할 때 방향 정보까지 함께 넣어주는 것이 핵심이다.
이유는 같은 칸에 도착했더라도 어떤 방향으로 들어왔는지에 따라 이후 갈 수 있는 경로와 추가로 필요한 거울 수가 달라지기 때문이다. 그래서 dist[x][y]만으로는 부족하고, dist[x][y][dir] 형태로 관리해야 한다.
여기에 맞춰서 상태를 (x, y, dir, cnt)로 두고 탐색을 진행했다. 현재 방향으로 한 칸 전진하는 경우는 거울 개수가 늘지 않고, 현재 칸이 !라면 좌회전 또는 우회전을 선택할 수 있으며 이때만 거울 개수가 1 증가한다.
시작 문에서는 네 방향 모두를 시작 상태로 넣어 주고, 다른 문에 도착했을 때의 최소 cnt를 답으로 사용한다. 결국 이 문제는 "칸"이 아니라 "칸 + 방향"을 정점으로 보는 최단 경로 문제다.
코드
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int n;
pair<int, int> start_door, end_door;
vector<string> room;
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
struct Node {
int x, y, dir, cnt;
};
int solve() {
int dist[50][50][4];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < 4; k++) {
dist[i][j][k] = 1e9;
}
}
}
queue<Node> q;
for (int i = 0; i < 4; i++) {
q.push({start_door.first, start_door.second, i, 0});
dist[start_door.first][start_door.second][i] = 0;
}
int ans = 1e9;
while (!q.empty()) {
Node cur = q.front();
q.pop();
if (cur.x == end_door.first && cur.y == end_door.second) {
ans = min(ans, cur.cnt);
continue;
}
if (dist[cur.x][cur.y][cur.dir] < cur.cnt) continue;
int nx = cur.x + dx[cur.dir];
int ny = cur.y + dy[cur.dir];
if (nx >= 0 && ny >= 0 && nx < n && ny < n && room[nx][ny] != '*') {
if (dist[nx][ny][cur.dir] > cur.cnt) {
dist[nx][ny][cur.dir] = cur.cnt;
q.push({nx, ny, cur.dir, cur.cnt});
}
}
if (room[cur.x][cur.y] == '!') {
int ndir1 = (cur.dir + 1) % 4;
int ndir2 = (cur.dir + 3) % 4;
if (dist[cur.x][cur.y][ndir1] > cur.cnt + 1) {
dist[cur.x][cur.y][ndir1] = cur.cnt + 1;
q.push({cur.x, cur.y, ndir1, cur.cnt + 1});
}
if (dist[cur.x][cur.y][ndir2] > cur.cnt + 1) {
dist[cur.x][cur.y][ndir2] = cur.cnt + 1;
q.push({cur.x, cur.y, ndir2, cur.cnt + 1});
}
}
}
return ans;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n;
room.resize(n);
bool has_start = false;
for (int i = 0; i < n; i++) {
cin >> room[i];
for (int j = 0; j < n; j++) {
if (room[i][j] == '#') {
if (has_start) {
end_door = make_pair(i, j);
} else {
has_start = true;
start_door = make_pair(i, j);
}
}
}
}
cout << solve() << '\n';
return 0;
}복잡도
- 시간 복잡도:
- 공간 복잡도:
마무리
같은 위치라도 방향이 다르면 전혀 다른 상태라는 점만 잡으면 풀이가 정리된다. 이 문제는 결국 방향 상태를 포함한 최단 경로 문제다.
