1. 문제 소개
이번에는 BFS 관련해서 풀이할 문제를 찾아보다가 적당히 어려울 것 같은 느낌 같아서 13460번 문제를 풀이했던 과정을 정리해 보려고 합니다.
https://www.acmicpc.net/problem/13460
13460번: 구슬 탈출 2
첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B'
www.acmicpc.net
아무리 어려워도 그래프 탐색인데, 라고 생각했는데 골드 1 난이도가 괜히 책정된 게 아닌 느낌으로 풀이하는데 굉장히 까다로웠습니다.
제 풀이 과정을 정리하기에 앞서 문제 설명을 간략하게 해보겠습니다.
우선 문제의 입력으로 보드의 크기인 세로(N), 가로(M)가 먼저 주어지고, N X M 사이즈의 보드에 대한 문자열이 다음 N 줄에 주어집니다.
위와 같은 보드를 상하좌우로 기울일 수 있을 때, 최소한의 횟수로 기울여서 빨간 공만을 구멍에 넣고 싶을 때 그 최솟값을 구하는 것이 문제의 요구 사항입니다. (파란 공이 빠지면, 빨간 공과 같이 빠져도 실패입니다!)
2. 내가 생각한 풀이 과정
저는 다음과 같은 순서로 풀이 과정을 생각했습니다.
1. 두 개의 공의 위치를 기준으로 BFS 수행
2. 빨간 공을 특정 방향으로 기울여서 움직인다.
3. 파란 공을 특정 방향으로 기울여서 움직인다.
4. 두 공의 도착 위치가 같은 경우 더 많이 움직인 공을 -1 만큼 이동시킨다.
5. 더 이상 공을 움직일 수 없는 경우 종료
6. 혹은 공이 하나라도 구멍에 빠지는 경우 종료
생각은 했지만, 풀이 과정에서 뇌 정지가 조금 와서 다른 분들의 모범 답안들을 조금씩 참고하면서 풀이했습니다..🙏🏻🙏🏻🙏🏻
우선 공의 좌표를 저장하는 pos 구조체를 다음과 같이 선언해서 사용했습니다.
다른 분들의 풀이를 참고하고, 저도 생각해본 결과 이전 시점에서 기울였던 방향이 현재에 영향을 미칠 수밖에 없고 그렇기 때문에 이전에 기울인 방향을 큐에 같이 담아서 BFS 탐색을 진행하도록 구현해야 했습니다. (제가 생각했을 땐 그랬습니다!)
1. 이전에 기울인 방향으로 똑같이 기울여도 공의 위치가 변하지 않음
2. 이전에 기울인 방향의 반대로 다시 기울이는 행위는 의미가 없음
바로 위의 두 가지 이유 때문에, 공의 현재 방향을 인자로 전달받았을 때, 반대 방향을 반환하는 함수를 만들어 사용했습니다.
int dx[] = { -1, 1, 0, 0 };
int dy[] = { 0, 0, -1, 1 };방향에 대한 배열은 위와 같이 사용했습니다.
이렇게 탐색해서 첫 번째 위치에서 네 방향으로 기울였을 때, 성공한 경우는 종료 후 BFS 함수 반환, 실패한 경우는 queue에 push 그중에서도 파란 공이 빠져서 실패한 경우는 건너뛰어서 queue에 push 되는 경우를 막았습니다.
또한 대부분의 그래프 탐색이나 이런 맵 혹은 보드?를 탐색할 때, 한 칸씩 이동을 진행하는데 이 문제의 경우 한 번 기울이면 벽을 만나거나 구멍을 만날 때까지 움직이기 때문에 while문을 활용해 벽을 만나는 경우까지 움직이되 벽에 도달한 경우 한 칸을 무르는 방식으로 구슬이 움직이도록 구현했습니다.
3. 내가 제출한 소스 코드 (C++)
/*
Date: 2022/08/23
Brief:
Reference:
*/
#include <iostream>
#include <string>
#include <cmath>
#include <queue>
#define MAX 11
using namespace std;
string map[MAX];
string arr[MAX];
int n, m;
int res = MAX;
struct pos{
int x;
int y;
};
pos redPos;
pos bluePos;
bool inRange(pos p) {
return (0 <= p.x && p.x < n && 0 <= p.y && p.y < m);
}
void input() {
for (int i = 0; i < n; i++) {
string tmp;
cin >> tmp;
arr[i]= tmp;
map[i] = "";
for (int j = 0; j < m; j++) {
if (tmp[j] == 'R' || tmp[j] == 'B') {
map[i] += '.';
if (tmp[j] == 'R') {
redPos.x = i, redPos.y = j;
}
else {
bluePos.x = i, bluePos.y = j;
}
continue;
}
map[i] += tmp[j];
}
}
}
// 현재 방향의 반대 방향을 반환하는 함수
int inverseDirection(int dir) {
if (dir == 0)
return 1;
else if (dir == 1)
return 0;
else if (dir == 2)
return 3;
else
return 2;
}
int distance(pos x, pos y) {
return abs(x.x - y.x) + abs(x.y - y.y);
}
void BFS(pos red, pos blue) {
// pos red, pos blue, dir, cnt
queue<pair<pair<pos, pos>, pair<int, int>>> q;
int dx[] = { -1, 1, 0, 0 };
int dy[] = { 0, 0, -1, 1 };
bool redFlag = false, blueFlag = false;
// 맨 처음 위치에서 4 개의 방향으로 움직여본다.
for (int i = 0; i < 4; i++) {
int dir = i;
pos next_red = red;
pos next_blue = blue;
while (1) {
if (map[next_red.x][next_red.y] == '#')
break;
else if (map[next_red.x][next_red.y] == 'O') {
redFlag = true;
break;
}
if (!inRange(next_red))
break;
next_red.x += dx[dir], next_red.y += dy[dir];
}
next_red.x -= dx[dir], next_red.y -= dy[dir];
while (1) {
if (map[next_blue.x][next_blue.y] == '#')
break;
else if (map[next_blue.x][next_blue.y] == 'O') {
blueFlag = true;
break;
}
if (!inRange(next_blue))
break;
next_blue.x += dx[dir], next_blue.y += dy[dir];
}
next_blue.x -= dx[dir], next_blue.y -= dy[dir];
// 두 구슬의 위치가 같은 경우
if (next_red.x == next_blue.x && next_red.y == next_blue.y) {
int redDist = distance(red, next_red);
int blueDist = distance(blue, next_blue);
// 더 많이 움직인 구슬을 한 칸 전으로 옮긴다.
if (redDist > blueDist) {
next_red.x -= dx[dir], next_red.y -= dy[dir];
}
else {
next_blue.x -= dx[dir], next_blue.y -= dy[dir];
}
}
// 빨간 공만 구멍에 넣는데 성공한 경우
if (redFlag && !blueFlag) {
res = 1;
redFlag = false, blueFlag = false;
return;
}
// 파란 공이 빠지면 의미 없음
else if (blueFlag) {
redFlag = false, blueFlag = false;
continue;
}
// 두 개의 공이 모두 구멍에 빠지지 않은 경우
else {
q.push({ {next_red, next_blue}, {dir, 1} });
}
}
while (!q.empty()) {
pos cur_red = q.front().first.first;
pos cur_blue = q.front().first.second;
int dir = q.front().second.first;
int cnt = q.front().second.second;
q.pop();
if (cnt >= res)
continue;
for (int i = 0; i < 4; i++) {
pos next_red = cur_red;
pos next_blue = cur_blue;
// 이전 진행 방향과 수평 방향은 탐색 의미가 없다.
if (i == dir || i == inverseDirection(dir))
continue;
int next_dir = i;
while (1) {
if (map[next_red.x][next_red.y] == '#')
break;
else if (map[next_red.x][next_red.y] == 'O') {
redFlag = true;
break;
}
next_red.x += dx[next_dir], next_red.y += dy[next_dir];
if (!inRange(next_red))
break;
}
next_red.x -= dx[next_dir], next_red.y -= dy[next_dir];
while (1) {
if (map[next_blue.x][next_blue.y] == '#')
break;
else if (map[next_blue.x][next_blue.y] == 'O') {
blueFlag = true;
break;
}
next_blue.x += dx[next_dir], next_blue.y += dy[next_dir];
if (!inRange(next_blue))
break;
}
next_blue.x -= dx[next_dir], next_blue.y -= dy[next_dir];
// 두 구슬의 위치가 같은 경우
if (next_red.x == next_blue.x && next_red.y == next_blue.y) {
int redDist = distance(cur_red, next_red);
int blueDist = distance(cur_blue, next_blue);
// 더 많이 움직인 구슬을 한 칸 전으로 옮긴다.
if (redDist > blueDist) {
next_red.x -= dx[next_dir], next_red.y -= dy[next_dir];
}
else {
next_blue.x -= dx[next_dir], next_blue.y -= dy[next_dir];
}
}
// 빨간 공만 구멍에 넣는데 성공한 경우
if (redFlag && !blueFlag) {
res = (res > cnt + 1) ? cnt + 1 : res;
return;
}
// 파란 공이 빠지면 의미 없음
else if (blueFlag) {
redFlag = false, blueFlag = false;
continue;
}
// 두 개의 공이 모두 구멍에 빠지지 않은 경우
else {
q.push({ {next_red, next_blue}, {next_dir, cnt + 1} });
}
}
}
return;
}
/*
1. 두 개의 공의 위치를 기준으로 BFS 수행
2. 빨간 공을 특정 방향으로 기울여서 움직인다.
3. 파란 공을 특정 방향으로 기울여서 움직인다.
4. 두 공의 도착 위치가 같은 경우 더 많이 움직인 공을 -1 만큼 이동시킨다.
5. 더 이상 공을 움직일 수 없는 경우 종료
6. 혹은 공이 하나라도 구멍에 빠지는 경우 종료
*/
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> m;
input();
BFS(redPos, bluePos);
if (res >= MAX) cout << -1;
else cout << res;
return 0;
}'Algorithm > PS' 카테고리의 다른 글
| 백준 - 17144번: 미세먼지 안녕! 문제 풀이 과정 정리 (C++) (3) | 2022.09.25 |
|---|---|
| 백준 2434번 - 기타 레슨, 이분 탐색 (Binary Search) 풀이 (C++) (0) | 2022.09.16 |
| 백준 2470번 - 두 용액, 대표적인 투 포인터 문제 (0) | 2022.09.08 |
| 백준 7562번 - 나이트의 이동, BFS를 이용한 그래프 순회 문제 (with C++) (0) | 2022.09.04 |
| BOJ - 2110번 공유기 설치 문제, 이분 탐색 문제 풀이! (with C++) (0) | 2022.08.28 |
댓글