문제 링크
https://www.acmicpc.net/problem/18188
문제
12월인 오늘, 크레이지 파크의 버블힐에는 첫 눈이 내렸다. 새하얗고 예쁜 첫 눈을 디지니와 함께 보고 싶은 다오는, 눈 오는 것을 핑계로 디지니와 데이트를 하고자 한다.
버블힐은 세로 H칸, 가로 W칸인 격자 모양이다. 그중 몇몇 칸에는 블록이 놓여져 있기에 지나갈 수 없다.
위에서 i번째 행, 왼쪽에서 j번째 열의 칸의 위치를 (i, j)라고 나타내자. 즉, 가장 왼쪽 위의 칸의 위치는 (1, 1)고, 가장 오른쪽 아래의 칸은 (H, W)다.
현재, 다오와 디지니는 버블힐의 서로 다른 칸 위에 서 있다. 다오는 블록이 없고 상하좌우로 인접한 칸으로 이동할 수 있다. 다오는 이렇게 이동하면서 디지니에게 가고자 한다.
모든 것이 다오의 생각대로 흘러가면 좋겠다만, 마리드는 다오를 짝사랑하기에, 다오와 디지니의 만남을 가만히 보고만 있지 않을 것이다. 마리드는 다오와 디지니가 서로 만나 데이트를 하는 것을 원하지 않는다. 고로 마리드는 다오의 움직임을 방해하면서, 다오가 디지니를 만나지 못하도록 할 것이다.
마리드가 다오를 방해하는 방법은 다음과 같다.
- 다오는 최대 N번 움직일 수 있다.
- 다오의 i번째 움직임은 마리드가 정해준 두 방향 중 하나를 택하여, 그 방향을 향해야 한다. 예를 들어, 마리드가 "세번째 움직임을 왼쪽과 윗쪽 중 한 방향으로 해라"고 명령하면, 다오는 세번째로 움직일 때, 왼쪽으로 가거나 윗쪽으로 가야 한다. 만약 마리드가 제시한 두 방향 중 어느 방향으로도 다오가 갈 수 없다면, 다오는 더 이상 움직일 수 없다.
만약 버블힐이 다음과 같이 생겼다고 하자. H = 2, W = 3, N = 2다. 현재, 다오는 (2, 1), 디지니는 (2, 3)에 위치해 있다. 또한 (1, 2)에는 블록이 있다.
<그림 1> 다오와 디지니, 그리고 마리드
마리드의 방해가 없었다면, 다오는 오른쪽으로 두 번 이동해서 사랑하는 디지니를 만날 수 있다. 그러나 마리드가 "첫 번째 움직임은 윗쪽과 오른쪽, 두번째 움직임은 윗쪽과 아랫쪽 중 한 방향으로 해라"고 명령한다면, 다오는 디지니를 만날 수 없다. 다오가 첫 번째 움직임으로 오른쪽을 택한다고 하더라도, 그 다음에 윗쪽이나 아랫쪽으로 움직일 수 없기 때문이다.
블록이 있는 칸이나 버블힐 바깥으로는 이동할 수 없음에 유의하라.
<그림 2> 마리드가 없을 때, 행복한 다오와 디지니
<그림 3> 마리드로 인해 만날 수 없는 다오와 디지니
다오와 디지니는 서로를 너무 보고 싶어 한다. 버블힐의 정보와 마리드의 방해에 관한 정보가 전부 주어질 때, 다오가 디지니를 만날 수 있는지 판별하는 프로그램을 작성하시오.
입력
첫 번째 줄에 버블힐의 세로와 가로의 칸 수를 의미하는 두 자연수 H과 W가 사이에 공백을 두고 주어진다.
두번째 줄부터 H개의 줄에 걸쳐, 버블힐의 정보가 주어진다. (i+1)번째 줄에는 길이 W의 문자열이 주어진다(1 ≤ i ≤ H). 이의 j번째 문자를 Ai, j라고 하자(1 ≤ j ≤ W). 이는 다음을 의미한다.
- Ai, j = '.'인 경우, 이는 (i, j)에 아무것도 없음을 의미한다.
- Ai, j = 'D'인 경우, 이는 (i, j)에 다오가 있음을 의미한다.
- Ai, j = 'Z'인 경우, 이는 (i, j)에 디지니가 있음을 의미한다.
- Ai, j = '@'인 경우, 이는 (i, j)에 블록이 있음을 의미한다.
(H+2)번째 줄에는 다오가 움직일 수 있는 최대 횟수를 의미하는 자연수 N가 주어진다.
(H+3)번째 줄부터 N개의 줄에 걸쳐, 마리드의 방해에 관한 정보가 주어진다. (H+i+2)번째 줄에는 두 문자 Bi와 Ci가 사이에 공백을 두고 주어진다(1 ≤ i ≤ N). 이는 다오가 i번째 움직임으로 Bi 방향이나 Ci 방향 중 하나를 택해야 함을 의미한다. 각 문자가 의미하는 방향은 다음과 같다(키보드에서 "WASD"의 배치를 생각하라).
- 'W'는 윗쪽을 의미한다.
- 'A'는 왼쪽을 의미한다.
- 'S'는 아랫쪽을 의미한다.
- 'D'는 오른쪽을 의미한다.
출력
만약 어떤 선택을 하더라도 다오가 디지니를 만날 수 없다면, 첫 번째 줄에 "NO"를 출력한다.
만약 다오가 디지니를 만날 수 있다면, 첫 번째 줄에 "YES"를 출력한다. 또한 두번째 줄에 다오가 어떻게 움직여야 하는지를 출력한다. 자세한 출력 형식은 입출력 예제를 참고하라.
다오가 디지니를 만날 수 있는 방법이 여러 가지라면, 그 중 아무거나 출력해도 정답으로 인정된다.
제한
모든 입력 데이터는 다음 조건을 만족한다.
- 2 ≤ H ≤ 20
- 2 ≤ W ≤ 20
- 1 ≤ N ≤ 20
- Ai, j는 '.', 'D', 'Z', '@' 중 하나다(1 ≤ i ≤ H, 1 ≤ j ≤ W).
- Ai, j 중 정확하게 하나는 'D'다(1 ≤ i ≤ H, 1 ≤ j ≤ W).
- Ai, j 중 정확하게 하나는 'Z'다(1 ≤ i ≤ H, 1 ≤ j ≤ W).
- Bi과 Ci는 'W', 'A', 'S', 'D' 중 하나다(1 ≤ i ≤ N).
- Bi ≠ Ci (1 ≤ i ≤ N).
예제 입력 1
2 3
.@.
D.Z
2
W D
W S
예제 출력 1
NO
첫번째 입출력 예제는 <그림 3>의 상황과 동일하다.
예제 입력 2
2 3
.@.
D.Z
2
A D
A D
예제 출력 2
YES
DD
두번째 입출력 예제의 경우, 다오가 오른쪽으로 두 번 움직이면 디지니를 만날 수 있다. 또한 이것이 다오가 디지니를 만나는 유일한 방법이다.
예제 입력 3
2 3
.Z.
.@D
3
W D
W S
A S
예제 출력 3
NO
세번째 입출력 예제의 경우, 다오는 어떻게 움직이더라도 디지니를 만날 수 없다. 만약 다오가 처음에 윗쪽으로 움직인다면, 두번째로 움직일 때에는 아랫쪽으로 갈 수밖에 없다. 왜냐하면 그때 다오는 (1, 3)에 서 있어서, 더 이상 윗쪽으로 움직일 수 없기 때문이다.
예제 입력 4
2 3
.Z.
.@D
3
W S
A S
W D
예제 출력 4
YES
WA
네번째 입출력 예제의 경우, 다오는 처음에 윗쪽으로, 두번째에 왼쪽으로 이동해서 디지니를 만날 수 있다. 다오는 세 번까지 움직일 수 있었으나, 두 번만에 디지니를 만났기 때문에 더 이상 움직일 필요가 없었다.
예제 입력 5
2 2
@@
ZD
4
A D
A D
A D
A D
예제 출력 5
YES
ADA
마지막 입출력 예제의 경우, 다오는 한 번만에 디지니를 만날 수 있다. 그러나 디지니가 있는 칸을 지나쳤다가 다시 돌아와도 정답으로 인정된다.
알고리즘 분류
- 백트래킹
- 그래프 탐색
풀이
최대 N번에 걸쳐서 다오는 디지니가 있는 곳에 도달해야 한다. 다오는 i번째로 행동할 때 마리드가 정해준 2가지의 방향으로만 이동할 수 있다.
격자의 크기가 20 X 20이고, N 역시 최대 20이므로 모든 경우의 수를 탐색해도 시간을 초과하지 않을 것이다.
또한 예제 5를 보면 이미 방문한 칸이라도 다시 방문할 수 있다고 나온다. 따라서 방문한 칸을 기록하지 않는다.
재귀를 사용해서 다오의 이동 경로를 정한다. 다오가 N번 행동했는데도 디지니를 찾지 못 했다면 더 이상 이동하지 않는다.
다오가 디지니를 만났다면 YES와 함께 다오의 이동 경로를 출력하고 종료한다.
다오가 어떤 경우라도 디지니를 만날 수 없다면 NO를 출력한다.
코드
#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#define MAX 21
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
using namespace std;
int H, W, N;
char B, C;
int MAP[MAX][MAX];
int MoveY[4] = { -1,0,1,0 };
int MoveX[4] = { 0,-1,0,1 };
vector<pair<int, int> > Vec;
pair<int, int> Start, End;
int change_Direction(char Dir) {
if (Dir == 'W') {
return 0;
}
else if (Dir == 'A') {
return 1;
}
else if (Dir == 'S') {
return 2;
}
return 3;
}
void input() {
cin >> H >> W;
for (int i = 0; i < H; i++) {
string S;
cin >> S;
for (int j = 0; j < W; j++) {
if (S[j] == 'D') {
Start = make_pair(i, j);
}
else if (S[j] == 'Z') {
End = make_pair(i, j);
}
else if (S[j] == '@') {
MAP[i][j] = -1;
}
}
}
cin >> N;
for (int i = 0; i < N; i++) {
cin >> B >> C;
Vec.push_back(make_pair(change_Direction(B), change_Direction(C)));
}
}
string reverse_Direction(int Dir) {
if (Dir == 0) {
return "W";
}
else if (Dir == 1) {
return "A";
}
else if (Dir == 2) {
return "S";
}
return "D";
}
void DFS(int Depth, string Direction, int Y, int X) {
if (make_pair(Y, X) == End) {
cout << "YES\n";
cout << Direction << "\n";
exit(0);
}
if (Depth == N) {
return;
}
int First = Vec[Depth].first;
int NextY = Y + MoveY[First];
int NextX = X + MoveX[First];
if ((NextY >= 0) && (NextY < H) && (NextX >= 0) && (NextX < W) && (MAP[NextY][NextX] != -1)) {
DFS(Depth + 1, Direction + reverse_Direction(First), NextY, NextX);
}
int Second = Vec[Depth].second;
NextY = Y + MoveY[Second];
NextX = X + MoveX[Second];
if ((NextY >= 0) && (NextY < H) && (NextX >= 0) && (NextX < W) && (MAP[NextY][NextX] != -1)) {
DFS(Depth + 1, Direction + reverse_Direction(Second), NextY, NextX);
}
}
void find_Answer() {
cout << "NO\n";
}
int main() {
FASTIO
input();
DFS(0, "", Start.first, Start.second);
find_Answer();
return 0;
}
'BOJ > Gold' 카테고리의 다른 글
[BOJ/Gold 4] 백준 19952 인성 문제 있어??(C++) (1) | 2023.01.11 |
---|---|
[BOJ/Gold 4] 백준 16569 화산쇄설류(C++) (0) | 2023.01.10 |
[BOJ/Gold 3] 백준 24513 좀비 바이러스(C++) (0) | 2023.01.05 |
[BOJ/Gold 4] 백준 25689 고속의 무작위 숫자 탐색(C++) (0) | 2023.01.04 |
[BOJ/Gold 5] 백준 25688 빠른 무작위 숫자 탐색(C++) (0) | 2023.01.03 |