이번 시간에는 백준 13460번 BFS를 활용한 구현문제를 풀어보겠습니다.
https://www.acmicpc.net/problem/13460
13460번: 구슬 탈출 2
첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B'
www.acmicpc.net
#include <iostream>
#include <vector>
#include <queue>
int BFS(std::pair<int, int>& initial_red, std::pair<int, int>& initial_blue);
std::vector<std::vector<char>> map_r;
std::vector<std::vector<char>> map_b;
int main() {
int N, M;
std::cin >> N >> M;
std::pair<int, int> initial_red;
std::pair<int, int> initial_blue;
map_r.resize(N);
map_b.resize(N);
for (int i = 0; i < N; ++i) {
for (int j = 0; j < M; ++j) {
char tmp;
std::cin >> tmp;
if (tmp == 'R') {
initial_red = { i,j };
map_r[i].push_back('R');
map_b[i].push_back('.');
continue;
}
if (tmp == 'B') {
initial_blue = { i,j };
map_b[i].push_back('B');
map_r[i].push_back('.');
continue;
}
map_r[i].push_back(tmp);
map_b[i].push_back(tmp);
}
}
std::cout << BFS(initial_red, initial_blue);
return 0;
}
int BFS(std::pair<int, int>& initial_red, std::pair<int, int>& initial_blue) {
std::queue<std::pair<std::pair<int, int>, int>> red_queue;
std::queue<std::pair<int, int>> blue_queue;
int count = 0;
red_queue.push({initial_red, count});
blue_queue.push(initial_blue);
bool visit[11][11][11][11] = {false,};
while (!red_queue.empty()) {
std::pair<int, int> red_tmp = red_queue.front().first;
count = red_queue.front().second;
if (count >= 10) return -1;
red_queue.pop();
std::pair<int, int> blue_tmp = blue_queue.front();
blue_queue.pop();
int R_y = red_tmp.first; int R_x = red_tmp.second;
int B_y = blue_tmp.first; int B_x = blue_tmp.second;
//오른쪽으로 기울이기
bool blue_goal = false;
bool red_goal = false;
while (true) {
if (map_r[B_y][B_x + 1] == 'O') {
blue_goal = true;
break;
}
if (map_b[R_y][R_x + 1] == 'O') {
red_goal = true;
} // 파랑색이 골에 도착시, 고려x 빨간색 도착시 find out
if (map_r[R_y][R_x + 1] != '#' && map_b[B_y][B_x + 1] != '#') { // 둘 다 벽
R_x++; B_x++;
continue;
}
else if (map_r[R_y][R_x + 1] != '#' && !(R_y == B_y && R_x + 1 == B_x)) { // 파랑 벽 and 빨강 옆 파랑x
R_x++;
continue;
}
else if (map_b[B_y][B_x + 1] != '#' && !(R_y == B_y && R_x == B_x + 1)) {
B_x++;
continue;
}
if((map_r[R_y][R_x + 1] == '#' && map_b[B_y][B_x + 1] == '#') ||
(map_b[B_y][B_x + 1] == '#' && (R_y == B_y && R_x + 1 == B_x)) ||
(map_r[R_y][R_x + 1] == '#' && (R_y == B_y && R_x == B_x + 1))) {
if (visit[R_y][R_x][B_y][B_x])
break;
if (red_goal)
break;
red_queue.push({ { R_y, R_x }, count + 1 });
blue_queue.push({ B_y, B_x });
visit[R_y][R_x][B_y][B_x] = true;
break;
}
}
if (red_goal && !blue_goal)
return count + 1;
blue_goal = false;
red_goal = false;
R_y = red_tmp.first; R_x = red_tmp.second;
B_y = blue_tmp.first; B_x = blue_tmp.second;
//왼쪽으로 기울이기
while (true) {
if (map_b[B_y][B_x - 1] == 'O') {
blue_goal = true;
break;
}
if (map_r[R_y][R_x - 1] == 'O') {
red_goal = true;
}
if (map_r[R_y][R_x - 1] != '#' && map_b[B_y][B_x - 1] != '#') {
R_x--; B_x--;
continue;
}
else if (map_r[R_y][R_x - 1] != '#' && !(R_y == B_y && R_x - 1 == B_x)) {
R_x--;
continue;
}
else if (map_b[B_y][B_x - 1] != '#' && !(R_y == B_y && R_x == B_x - 1)) {
B_x--;
continue;
}
if ((map_r[R_y][R_x - 1] == '#' && map_b[B_y][B_x - 1] == '#') ||
(map_b[B_y][B_x - 1] == '#' && (R_y == B_y && R_x - 1 == B_x)) ||
(map_r[R_y][R_x - 1] == '#' && (R_y == B_y && R_x == B_x - 1))) {
if (visit[R_y][R_x][B_y][B_x])
break;
if (red_goal)
break;
red_queue.push({ { R_y, R_x }, count + 1});
blue_queue.push({ B_y, B_x });
visit[R_y][R_x][B_y][B_x] = true;
break;
}
}
if (red_goal && !blue_goal)
return count + 1;
blue_goal = false;
red_goal = false;
R_y = red_tmp.first; R_x = red_tmp.second;
B_y = blue_tmp.first; B_x = blue_tmp.second;
//위쪽으로 기울이기
while (true) {
if (map_b[B_y - 1][B_x] == 'O') {
blue_goal = true;
break;
}
if (map_r[R_y - 1][R_x] == 'O') {
red_goal = true;
}
if (map_r[R_y - 1][R_x] != '#' && map_b[B_y - 1][B_x] != '#') {
R_y--; B_y--;
continue;
}
else if (map_r[R_y - 1][R_x] != '#' && !(R_y - 1 == B_y && R_x == B_x)) {
R_y--;
continue;
}
else if (map_b[B_y - 1][B_x] != '#' && !(R_y == B_y - 1 && R_x == B_x)) {
B_y--;
continue;
}
if ((map_r[R_y - 1][R_x] == '#' && map_b[B_y - 1][B_x] == '#') ||
(map_b[B_y - 1][B_x] == '#' && (R_y - 1== B_y && R_x == B_x)) ||
(map_r[R_y - 1][R_x] == '#' && (R_y == B_y - 1 && R_x == B_x))) {
if (visit[R_y][R_x][B_y][B_x])
break;
if (red_goal)
break;
red_queue.push({ { R_y, R_x }, count + 1 });
blue_queue.push({ B_y, B_x });
visit[R_y][R_x][B_y][B_x] = true;
break;
}
}
if (red_goal && !blue_goal)
return count + 1;
blue_goal = false;
red_goal = false;
R_y = red_tmp.first; R_x = red_tmp.second;
B_y = blue_tmp.first; B_x = blue_tmp.second;
//아래쪽으로 기울이기
while (true) {
if (map_b[B_y + 1][B_x] == 'O') {
blue_goal = true;
break;
}
if (map_r[R_y + 1][R_x] == 'O') {
red_goal = true;
}
if (map_r[R_y + 1][R_x] != '#' && map_b[B_y + 1][B_x] != '#') {
R_y++; B_y++;
continue;
}
else if (map_r[R_y + 1][R_x] != '#' && !(R_y + 1 == B_y && R_x == B_x)) {
R_y++;
continue;
}
else if (map_b[B_y + 1][B_x] != '#' && !(R_y == B_y + 1 && R_x == B_x)) {
B_y++;
continue;
}
if ((map_r[R_y + 1][R_x] == '#' && map_b[B_y + 1][B_x] == '#') ||
(map_b[B_y + 1][B_x] == '#' && (R_y + 1 == B_y && R_x == B_x)) ||
(map_r[R_y + 1][R_x] == '#' && (R_y == B_y + 1 && R_x == B_x))) {
if (visit[R_y][R_x][B_y][B_x])
break;
if (red_goal)
break;
red_queue.push({ { R_y, R_x }, count + 1 });
blue_queue.push({ B_y, B_x });
visit[R_y][R_x][B_y][B_x] = true;
break;
}
}
if (red_goal && !blue_goal)
return count + 1;
}
return -1;
}struct나 class를 사용해서 구현했으면, 더 짧게 가능했을 것으로 보인다.
간과한 점: 빨강이 파랑보다 먼저 goal에 도착하고 후에 파랑이 goal에 도착했을 때
'백준' 카테고리의 다른 글
| 백준 3190번(Gold 4) (1) | 2023.11.22 |
|---|---|
| 백준 12100번(Gold 2) (1) | 2023.11.22 |
| 백준 15686번(Gold 4) (1) | 2023.10.13 |
| 백준 2015번(Gold 4) (0) | 2023.10.05 |
| 백준 2960번(Silver 4) (1) | 2023.10.05 |