1. 문제
- 백준, 골드 1, https://www.acmicpc.net/problem/13460
- 풀이 날짜: 2025.3.21.
- 풀이 시간: 10:52~12:24(1시간 32분)
- 알고리즘 분류: 구현, 그래프 탐색, 시뮬레이션, 너비 우선 탐색(BFS)
- 사용 언어: C++
2. 문제 해설
상, 하, 좌, 우로 이동시킨다는 것은, 위쪽, 아랫쪽, 왼쪽, 오른쪽으로 옮겼을 때에 대한 가능성 트리 노드를 순회하는 것과 같다고 생각할 수 있다.
그러면 해당 문제는 이동횟수를 최소화하는 최단 경로 그래프 탐색 문제로 생각할 수 있으므로, 간선의 개수가 이동 횟수인 지금은 BFS를 통해서 탐색하면 된다.
탐색할 수 있는 경우의 수는 4가지이고 깊이는 최대 10이므로(10회보다 더 이동할 경우 탐색하지 않음), 경우의 수는 $4^{10}=2^{20}$으로 약 1백 만 번이 된다. 이는 1초 내에 충분히 해결할 수 있는 시간이므로 BFS로 모두 탐색을 진행하도록 한다.
이때 BFS로 탐색하려면, 가능성 트리의 노드에는 다음 정보가 들어가야 한다.
- 현재 이동 횟수
- 빨강 구슬의 위치(x, y)
- 파랑 구슬의 위치(x, y)
맵 전체를 저장하기엔 너무 메모리가 많이 필요하므로, 풀이 시에 빨강 구슬의 위치와 파랑 구슬의 위치만 저장하도록 했다. 정보가 여러 개 필요하므로, Struct CaseNode로 정의하도록 했다.
#define PairInt pair<int, int>
struct CaseNode
{
int movements;
PairInt redPos;
PairInt bluePos;
CaseNode(int inMovements, PairInt inRedPos, PairInt inBluePos)
: movements(inMovements)
, redPos(inRedPos)
, bluePos(inBluePos)
{}
};
이때 pair<int, int>에 좌표 값이 저장되는데, <y, x> 순으로 저장하도록 했다.
보통 이런 유형의 문제는 엣지 케이스가 문제가 된다.
여기서는 어떤 점이 문제가 되었는지 나열해보려 한다.
2.1. 문제 1: 빨강 구슬과 파랑 구슬의 이동 순서?
여기서는 이동시켜야 하는 구슬이 두 개이다. 둘 중 무엇을 먼저 움직이냐에 따라 결과가 다르게 나오니, 그 순서를 주의해야 한다.
- 이동시키려는 방향에 더 가까운 쪽 구슬을 먼저 이동시켜야 한다.
- 예시: 만약 왼쪽으로 이동시킬 경우, 왼쪽에 있는 구슬을 먼저 이동시켜야 한다.
이를 위해 이동하는 방향에 따라 어느 구슬을 먼저 이동시킬지 결정하는 함수를 생성하였다.
bool IsRedFirst(PairInt redPos, PairInt bluePos, int dx, int dy)
{
if (dx == 0)
{
if (redPos.first < bluePos.first)
return dy < 0;
else
return dy > 0;
}
else
{
if (redPos.second < bluePos.second)
return dx < 0;
else
return dx > 0;
}
}
위 함수는 빨강 구슬이 먼저 오는지 아닌지를 계산하는 함수이다.
빨강 구슬이 먼저 이동되어야 할 경우 true, 아니면 false를 반환한다.
이때, 구슬의 이동 방향은 dx, dy로 정의하도록 했다.
map의 x, y는 위쪽으로 갈수록 y가 작아지고 아래쪽으로 갈수록 y가 커지는 식으로 정의했다. x도 마찬가지로, 왼쪽으로 가면 x가 작아지고 오른쪽으로 갈수록 x가 커진다.
첫 번째 if문을 예시로 설명하자면, 위쪽으로 이동할 경우 위쪽 구슬이 더 빨리 움직이도록 순서를 처리한다.
dx == 0이고 빨강 구슬의 y가 파랑 구슬의 y보다 작아서(redPos.first < bluePos.first) 빨강 구슬이 더 위쪽에 있다고 치자. 이 경우엔 위쪽으로 움직일 땐 빨강 구슬이 먼저, 아랫쪽으로 움직일 땐 파랑 구슬이 먼저 움직여야 한다. 이 조건을 dy < 0으로 정의하도록 했다.
비슷한 논리로, 다른 방향도 정의할 수 있다.
이렇게 이동 방향에 따른 이동 순서를 정의했다면, 다음은 이동을 정의할 수 있다.
구슬이 이동할 땐 이동 방향에 ‘.’가 있거나 ‘O’가 있을 때만 이동할 수 있다. 구슬이 각각 한 칸을 차지하므로, 구슬이 있을 땐 움직이지 못해야 한다. 그리고 ‘O’가 있을 땐 구멍이 있는 것이므로 바로 종료하도록 한다.
빨강 구슬, 파랑 구슬 모두 움직일 수 있게 하기 위해서, 목표 지점에 도달하면 무조건 true, 아니면 false를 반환하도록 했다. 만약 빨강 구슬에서 TryMove()==true이면 성공이고 파랑 구슬에서 TryMove()==true면 실패로 간주해야 할 것이다.
이동을 완료한 위치도 기록해야 하니, 위치 PairInt에 대한 out 변수를 두었다.
이 논리대로 바로 구현해보자.
bool TryMove(PairInt startPoint, int dx, int dy, string map[], PairInt& out)
{
bool success = false;
int y = startPoint.first;
int x = startPoint.second;
while (map[y+dy][x+dx] == '.' || map[y+dy][x+dx] == 'O')
{
y += dy;
x += dx;
if (map[y][x] == 'O')
{
success = true;
break;
}
}
out = make_pair(y, x);
return success;
}
2.2. 문제 2: 빨강구슬과 파랑구슬이 각각 서로에게 막히는 경우
구슬은 각각 1칸을 차지한다고 한다. 따라서, 이동할 때 빨강 구슬이 파랑 구슬을 막거나, 파랑 구슬이 빨강 구슬을 막는 경우를 고려해야 한다.
// 빨강 구슬과 파랑 구슬이 서로 막히는지 확인
입력 1
4 10
##########
#......BR#
#.O......#
##########
정답: 2
// 이전 위치를 잘 처리했는지 확인하기
입력 2
6 8
########
#.O....#
##B#..R#
#..##..#
##...###
########
정답: 4(아래, 오른쪽, 위쪽, 왼쪽)
// 출처: <https://www.acmicpc.net/board/view/153294>
하지만 맵에 이 구슬을 모두 기록했다간, 다른 케이스를 고려할 때 문제가 생기기 쉽다.
그러므로 빨강 구슬과 파랑 구슬 중 먼저 움직인 구슬의 위치만 맵에 그려주도록 해서, 나중에 움직이는 구슬은 먼저 움직인 구슬에 막히도록 해줄 것이다.
예를 들어, 빨강 구슬이 먼저 움직일 땐 빨강 구슬의 이동 위치를 기록해주고, 파랑 구슬이 움직인 뒤엔 빨강 구슬의 위치를 지워주도록 한다.
이러한 논리대로, 모든 가능성 노드마다 어떻게 처리해야 할지 기록하면 이렇게 된다.
queue<CaseNode> q;
int dy[] = { -1, 0, 0, 1 };
int dx[] = { 0, -1, 1, 0 };
PairInt redPos, bluePos;
// ...
CaseNode cur = q.front();
q.pop();
if (cur.movements >= 10) // 이동 횟수가 10 이상이 되면 종료
continue;
// 모든 방향마다 이동시키기
for (int dir = 0; dir < 4; dir++)
{
// 무슨 구슬을 먼저 움직일 것인가?
if (IsRedFirst(cur.redPos, cur.bluePos, dx[dir], dy[dir]))
{ // 빨강 구슬 먼저 이동
// 빨강 구슬 움직이기
if (TryMove(cur.redPos, dx[dir], dy[dir], map, redPos))
{
// 구멍에 들어가면 성공!
cout << cur.movements + 1 << "\\n";
return 0;
}
// 빨강 구슬 위치 기록하기
map[redPos.first][redPos.second] = 'R';
// 파랑 구슬 움직이기
if (TryMove(cur.bluePos, dx[dir], dy[dir], map, bluePos))
{
// 파랑 구슬이 구멍에 들어가면 실패...
map[redPos.first][redPos.second] = '.';
continue; // Fail
}
// 빨강 구슬 위치 지워주기
map[redPos.first][redPos.second] = '.';
// 구슬이 안 움직였으면 무시
if (cur.redPos == redPos && cur.bluePos == bluePos)
continue;
q.push(CaseNode(cur.movements + 1, redPos, bluePos));
}
else
{ // 파랑 구슬 먼저 이동
// 파랑 구슬 움직이기
if (TryMove(cur.bluePos, dx[dir], dy[dir], map, bluePos))
continue; // 파랑 구슬이 구멍에 들어가면 Fail
// 파랑 구슬 위치 기록하기
map[bluePos.first][bluePos.second] = 'B';
// 빨강 구슬 이동하기
if (TryMove(cur.redPos, dx[dir], dy[dir], map, redPos))
{
// 구멍에 들어가면 성공!
cout << cur.movements + 1 << "\\n";
return 0;
}
// 파랑 구슬 위치 지우기
map[bluePos.first][bluePos.second] = '.';
// 구슬이 안 움직였으면 무시
if (cur.redPos == redPos && cur.bluePos == bluePos)
continue;
q.push(CaseNode(cur.movements + 1, redPos, bluePos));
}
}
이렇게 하면 구슬 서로가 서로에게 막혀서 정상적인 결과를 얻을 수 있다.
하지만 여전히 문제는 남아 있다.
2.3. 문제 3: 구멍에 동시에 구슬이 들어갈 경우
여기서 문제의 조건을 하나 더 고려해야 한다.
문제 조건: 빨간 구슬과 파란 구슬이 동시에 구멍에 빠져도 실패이다.
해당 조건을 고려하는 걸 깜빡해서 실패하게 되었다.
구멍에 빨간 구슬이 들어가더라도, 파랑 구슬도 함께 들어가면 그 케이스는 실패로 간주해야 한다.
입력 3
5 4
####
#.O#
#R.#
#B.#
####
정답: 2 (위, 오른쪽)
// 출처: <https://www.acmicpc.net/board/view/139852>
위 케이스를 보면, 위로 이동시킨 후 오른쪽으로 이동시키는 것은 정답이다.
반면, 오른쪽으로 이동시킨 후 위로 이동시키면 빨강, 파랑 구슬이 동시에 구멍에 들어가므로 실패다.
즉, 빨강 구슬을 먼저 이동시킬 때, 빨강 구슬이 먼저 들어간 후에 파랑 구슬이 들어가지 않았는지 확인해주어야 한다.
이 모든 걸 고려한 최종 코드는 다음과 같다.
#include <iostream>
#include <string>
#include <queue>
#define PairInt pair<int, int>
using namespace std;
struct CaseNode
{
int movements;
PairInt redPos;
PairInt bluePos;
CaseNode(int inMovements, PairInt inRedPos, PairInt inBluePos)
: movements(inMovements)
, redPos(inRedPos)
, bluePos(inBluePos)
{}
};
bool TryMove(PairInt startPoint, int dx, int dy, string map[], PairInt& out)
{
bool success = false;
int y = startPoint.first;
int x = startPoint.second;
while (map[y+dy][x+dx] == '.' || map[y+dy][x+dx] == 'O')
{
y += dy;
x += dx;
if (map[y][x] == 'O')
{
success = true;
break;
}
}
out = make_pair(y, x);
return success;
}
bool IsRedFirst(PairInt redPos, PairInt bluePos, int dx, int dy)
{
if (dx == 0)
{
if (redPos.first < bluePos.first)
return dy < 0;
else
return dy > 0;
}
else
{
if (redPos.second < bluePos.second)
return dx < 0;
else
return dx > 0;
}
}
int main()
{
int n, m;
string map[10];
queue<CaseNode> q;
int dy[] = { -1, 0, 0, 1 };
int dx[] = { 0, -1, 1, 0 };
PairInt redPos, bluePos;
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 0; i < n; i++)
{
cin >> map[i];
for (int j = 0; j < m; j++)
{
if (map[i][j] == 'R')
redPos = make_pair(i, j);
else if (map[i][j] == 'B')
bluePos = make_pair(i, j);
}
}
q.push(CaseNode(0, redPos, bluePos));
map[redPos.first][redPos.second] = '.';
map[bluePos.first][bluePos.second] = '.';
while (!q.empty())
{
CaseNode cur = q.front();
q.pop();
if (cur.movements >= 10)
continue;
for (int dir = 0; dir < 4; dir++)
{
bool success = false;
if (IsRedFirst(cur.redPos, cur.bluePos, dx[dir], dy[dir]))
{
// move red ball
if (TryMove(cur.redPos, dx[dir], dy[dir], map, redPos))
{
success = true;
}
if (map[redPos.first][redPos.second] == '.')
map[redPos.first][redPos.second] = 'R';
// move blue ball
if (TryMove(cur.bluePos, dx[dir], dy[dir], map, bluePos))
{
if (map[redPos.first][redPos.second] == 'R')
map[redPos.first][redPos.second] = '.';
continue; // Fail
}
if (map[redPos.first][redPos.second] == 'R')
map[redPos.first][redPos.second] = '.';
if (cur.redPos == redPos && cur.bluePos == bluePos)
continue;
// 빨강 공만 들어갔을 경우 성공
if (success)
{
cout << cur.movements + 1 << "\\n";
return 0;
}
q.push(CaseNode(cur.movements + 1, redPos, bluePos));
}
else
{
// move blue ball
if (TryMove(cur.bluePos, dx[dir], dy[dir], map, bluePos))
continue; // Fail
if (map[bluePos.first][bluePos.second] == '.')
map[bluePos.first][bluePos.second] = 'B';
// move red ball
if (TryMove(cur.redPos, dx[dir], dy[dir], map, redPos))
{
cout << cur.movements + 1 << "\\n";
return 0;
}
if (map[bluePos.first][bluePos.second] == 'B')
map[bluePos.first][bluePos.second] = '.';
if (cur.redPos == redPos && cur.bluePos == bluePos)
continue;
q.push(CaseNode(cur.movements + 1, redPos, bluePos));
}
}
}
cout << "-1\\n";
return 0;
}
'Problem Solving > Backjoon' 카테고리의 다른 글
| 백준 1206번 - 사람의 수(C++) (0) | 2025.04.03 |
|---|---|
| 백준 28116번 - 선택 정렬의 이동 거리 (0) | 2025.03.22 |
| 백준 11444번 - 피보나치 수 6(C++) (0) | 2025.03.18 |
| 백준 9328번 - 열쇠(C++) 풀이 정리 (0) | 2025.02.26 |
| 백준 2075번 - N번째 큰 수: 약간 더 빠른 코드 (1) | 2025.02.04 |
댓글