백준
백준 15644 구슬 탈출3
콩순이냉장고
2021. 11. 2. 14:37
문제 URL : https://www.acmicpc.net/problem/15644
15644번: 구슬 탈출 3
첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B'
www.acmicpc.net
문제 접근법 :
두공이 움직이는것은 BFS를 이용하면 간단하니 이용하면 되니 생략하겠습니다.
하지만 두공의 충돌여부가 문제입니다.
충돌처리만 잘하시면 문제는없습니다.
아래 그림을 보시면
공이 오른쪽으로 움직여야할때 빨강공과 파랑공은 같은자리에서 충돌하게 됩니다. 그러나 두공이 같은자리에 있을수는 없죠 누가 먼저 벽에 도달했는지 확인합니다. 빨강공이 더 적게 움직였으니 빨강공이 먼저 도달했다는것을 알수있습니다. 그렇기에 충돌할경우 움직인횟수가 더 많은녀석이 한칸 뒤로 움직여주면 됩니다.
그리고 마지막으로 움직였던 이동은 q안에 벡터를 넣어서 모두 저장해주면 됩니다
소스코드 :
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
|
#include <bits/stdc++.h>
using namespace std;
int n, m;
int ry, rx, by, bx, fy, fx;
char board[11][11];
int dy[4] = { -1,0,1,0 };
int dx[4] = { 0,1,0,-1 };
void input() {
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> board[i][j];
if (board[i][j] == 'R') {
tie(ry, rx) = { i,j };
board[i][j] = '.';
}
else if (board[i][j] == 'B') {
tie(by, bx) = { i,j };
board[i][j] = '.';
}
else if (board[i][j] == 'O') {
tie(fy, fx) = { i, j };
}
}
}
}
void nextMove(int& ny, int& nx, int& cnt,int i) {
while (board[ny][nx] == '.') {
ny += dy[i];
nx += dx[i];
cnt++;
if (board[ny][nx] == '#') {
ny -= dy[i];
nx -= dx[i];
break;
}
}
}
void print(int ny1,int nx1,int ny2,int nx2) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (i == ny1 && j == nx1)
cout << "R" << " ";
else if (i == ny2 && j == nx2)
cout << "B" << " ";
else
cout << board[i][j]<<" ";
}
cout << endl;
}
cout << endl;
}
void bfs() {
int check[11][11][11][11] = { 0 };
queue<tuple<int, int, int, int, vector<int>>>q;
vector<int> v;
q.push({ ry,rx,by,bx,v });
check[ry][rx][by][bx] = 1;
char move[]= "URDL";
while (!q.empty()) {
tie(ry, rx, by, bx, v) = q.front();
q.pop();
if (v.size() > 10)
break;
if (ry == fy && rx == fx && !(by == fy && bx == fx)) {
cout << v.size() << "\n";
for (int i : v)
cout << move[i];
cout << "\n";
return;
}
for (int i = 0; i < 4; i++) {
int ny1, nx1, ny2, nx2;
int cnt1 = 0, cnt2 = 0;
tie(ny1, nx1, ny2, nx2) = { ry,rx,by,bx };
nextMove(ny1, nx1, cnt1, i);
nextMove(ny2, nx2, cnt2, i);
//두공이 충돌할경우
if (ny1 == ny2 && nx1 == nx2) {
//목표지점이면 무시
if (board[ny1][nx1] == 'O')continue;
//빨강공이 먼저 도착하면 파랑공 1칸 뒤로
if (cnt1 < cnt2) {
ny2 -= dy[i];
nx2 -= dx[i];
}
else {
//그 반대
ny1 -= dy[i];
nx1 -= dx[i];
}
}
//print(ny1,nx1,ny2,nx2);
if (check[ny1][nx1][ny2][nx2]==0) {
v.push_back(i);
q.push({ ny1,nx1,ny2,nx2,v });
check[ny1][nx1][ny2][nx2] = 1;
v.pop_back();
}
}
}
cout << -1 << "\n";
}
void solve() {
bfs();
}
int main() {
cin.tie(0);
cout.tie(0);
input();
solve();
return 0;
}
|
cs |
궁금한점 혹은 모르는점 논리적인 오류등 어떤질문이든 댓글은 언제나 환영입니다.