[C++] 백준 13460 구슬 탈출 2

Posted by 시골친구들

2020. 5. 26. 00:40

문제 링크

https://www.acmicpc.net/problem/13460

13460번: 구슬 탈출 2

첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B'

www.acmicpc.net

문제 접근

BFS 알고리즘의 문제인데, 신경써야할 대상이 2개 (빨간 공, 파란 공)라서 매우 까다롭습니다.

먼저 코딩부터 시작하면 중간에 흐름을 놓치기 쉽습니다. 단계적으로 천천히 접근해보도록 하겠습니다.

1) 데이터 형태 정의

typedef struct ball {
	int y, x;
};
typedef struct balls {
	ball red;
	ball blue;
	int count;
};

ball 구조체는 빨간 공, 파란 공을 나타낼 구조체입니다.

balls 구조체는 BFS 탐색을 위해서 큐에 빨간 공과 파란 공을 묶어서 담기 위한 구조체이며, count는 판을 기울인 횟수를 기록합니다.

2) 데이터 입력받기

ball red, blue;
char map[MAX][MAX];
void input() {
	cin >> N >> M;
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < M; ++j) {
			cin >> map[i][j];
			if (map[i][j] == 'R') { // 빨간공에 대한 정보 담기
				red = { i, j };
				map[i][j] = '.'; // 현재 위치는 빈공간으로 둔다.
			}
			else if (map[i][j] == 'B') { // 파란공에 대한 정보 담기
				blue = { i, j };
				map[i][j] = '.'; // 현재 위치는 빈공간으로 둔다.
			}
		}
	}
}

char형으로 map에 데이터를 입력해줍니다. red와 blue는 좌표로 다룰 것이므로, map에 'R'과 'B'는 지워줍니다.

3) 공의 이동을 함수로 구현하기

const pair<int, int> direction[4] = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };
bool isMovable(int y, int x, int other_y, int other_x) {
	if (map[y][x] == '#') return false;
	if (y == other_y && x == other_x) { // 다른 공과 좌표가 같은 경우
		if (map[y][x] == 'O') return true; // 목적지인 경우에는 겹치기 허용
		else return false; // 목적지가 아니면 공끼리 겹치기 허용하지 않음
	}
	return true; // 벽, 공 겹치는 경우 외에는 이동 가능
}

ball move(ball obj, ball other, int d) {
	int ny, nx;
	while (1) {
		ny = obj.y + direction[d].first;
		nx = obj.x + direction[d].second;
		if (!isMovable(ny, nx, other.y, other.x)) break;
		if (map[ny][nx] == 'O') { // 목적지인 경우에는 이동하고 종료
			obj.y = ny; obj.x = nx;
			break;
		}
		obj.y = ny; obj.x = nx; // 이상 없으면 해당 좌표로 이동
	}
	return obj;
}

direction[4] = {오른쪽, 아래, 왼쪽, 위}로 정의를 해준 뒤, 공 1개를 방향 d로 움직이는 함수를 구현합니다. isMovable 함수를 통해서 공이 움직일 수 있는 경우와 움직일 수 없는 경우를 꼼꼼히 구분해줍니다. move함수를 통하여 공 1개의 움직임을 다른 공과 겹치지 않게 방향 d로 움직여줍니다. 판이 기울었기 때문에 공은 어떤 다른 오브젝트에 부딪혀서 움직이지 못할때까지 이동할 것입니다.

4) 판을 기울이는 함수 구현하기

// 주어진 조건에 판을 기울여서 공을 움직인 뒤, 공의 이동한 좌표를 반환하는 함수
// 공의 좌표가 겹치는 경우는 오직 목적지에 도착했을 경우이다.
balls tilt(balls current, int direct) {
	balls next = current;
	if (direct == 0) { // 우측으로 기울이는 경우 (x++)
		if (current.red.x > current.blue.x) { // x가 더 큰 쪽이 먼저 움직여야 한다.
			next.red = move(current.red, current.blue, direct);
			next.blue = move(current.blue, next.red, direct);
		}
		else { // blue가 더 우측에 있는 경우, blue 먼저 이동
			next.blue = move(current.blue, current.red, direct);
			next.red = move(current.red, next.blue, direct);
		}
	} 
	else if (direct == 1) { // 아래로 기울이는 경우 (y++)
		if (current.red.y > current.blue.y) { // y가 더 큰 쪽이 먼저 움직여야 한다.
			next.red = move(current.red, current.blue, direct);
			next.blue = move(current.blue, next.red, direct);
		}
		else { // blue가 더 하단에 있는 경우, blue 먼저 이동
			next.blue = move(current.blue, current.red, direct);
			next.red = move(current.red, next.blue, direct);
		}
	}
	else if (direct == 2) { // 좌측으로 기울이는 경우 (x--)
		if (current.red.x < current.blue.x) { // x가 더 작은 쪽이 먼저 움직여야 한다.
			next.red = move(current.red, current.blue, direct);
			next.blue = move(current.blue, next.red, direct);
		}
		else { // blue가 더 좌측에 있는 경우, blue 먼저 이동
			next.blue = move(current.blue, current.red, direct);
			next.red = move(current.red, next.blue, direct);
		}
	}
	else if (direct == 3) { // 상단으로 기울이는 경우 (y--)
		if (current.red.y < current.blue.y) { // y가 더 작은 쪽이 먼저 움직여야 한다.
			next.red = move(current.red, current.blue, direct);
			next.blue = move(current.blue, next.red, direct);
		}
		else { // blue가 더 좌측에 있는 경우, blue 먼저 이동
			next.blue = move(current.blue, current.red, direct);
			next.red = move(current.red, next.blue, direct);
		}
	}
	return next; // 이동한 좌표를 반환한다.
}

판이 기울어졌을때 먼저 고려해야할 것은 '어떤 공을 먼저 움직일 것인가?' 입니다. 저는 방향별로 기울여진 방향쪽에 더 가까운 공을 먼저 움직이는 방법을 택하였습니다. 빨간 공과 파란 공의 현재 위치 정보가 담긴 balls current를 입력 받아서, 주어진 방향 direct로 이동한 좌표 balls next를 반환합니다.

5) BFS 구현

int bfs() {
	queue<balls> q;
	q.push({ red, blue, 1 });
	visit[red.y][red.x][blue.y][blue.x] = 1;

	bool break_flag = false;
	int level_size, ret = INF;
	balls current, next;
	while (!q.empty()) {
		level_size = q.size();
		while (level_size--) {
			current = q.front(); q.pop();
			if (current.count > 10) {
				break_flag = true;
				break;
			}
			for (int direct = 0; direct < 4; ++direct) {
				next = tilt(current, direct);
				if (map[next.red.y][next.red.x] == 'O') { // red가 빠져나갔다면
					if (map[next.blue.y][next.blue.x] == 'O') { // blue도 빠져나갔다면
						visit[next.red.y][next.red.x][next.blue.y][next.blue.x] = 1;
						continue; // 다른 방향으로 기울여본다.
					}
					else { // red만 빠져나갔다면
						ret = min(ret, current.count); // 최소값 갱신
					}
				}
				else if (map[next.blue.y][next.blue.x] == 'O') { // blue만 빠져나갔다면
					visit[next.red.y][next.red.x][next.blue.y][next.blue.x] = 1;
					continue; // 다른 방향으로 기울여본다.
				}
				else if (!visit[next.red.y][next.red.x][next.blue.y][next.blue.x]) {
					++next.count;
					q.push(next);
					visit[next.red.y][next.red.x][next.blue.y][next.blue.x] = 1;
				}
			}
		}
		if (break_flag) break;
	}
	if (ret == INF) return -1;
	else return ret;
}

BFS를 구현할 때 가장 중요하다고 생각이 들었던 것은, visit를 4차원으로 표현하는 것이었습니다. 판이 기울여지면 공은 기울여진 방향 d로 끝까지 이동하고, 빨간 공, 파란 공 둘의 위치를 모두 고려해야 하므로 4차원으로 사용하였습니다.

저는 빨간 공과 파란 공을 목적지에 도달한 경우에만 겹치게 하였기 때문에, 둘 다 겹치는 경우, 한 가지만 겹치는 경우로 나누어서 결과를 구분할 수 있었습니다.

전체 소스 코드

#include <queue>
#include <iostream>
#include <algorithm>
#define MAX 10
using namespace std;
typedef struct ball {
	int y, x;
};
typedef struct balls {
	ball red;
	ball blue;
	int count;
};
ball red, blue;
char map[MAX][MAX];
const int INF = 99999999;
int N, M, visit[MAX][MAX][MAX][MAX];
const pair<int, int> direction[4] = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };

void input() {
	cin >> N >> M;
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < M; ++j) {
			cin >> map[i][j];
			if (map[i][j] == 'R') { // 빨간공에 대한 정보 담기
				red = { i, j };
				map[i][j] = '.'; // 현재 위치는 빈공간으로 둔다.
			}
			else if (map[i][j] == 'B') { // 파란공에 대한 정보 담기
				blue = { i, j };
				map[i][j] = '.'; // 현재 위치는 빈공간으로 둔다.
			}
		}
	}
}

bool isMovable(int y, int x, int other_y, int other_x) {
	if (map[y][x] == '#') return false;
	if (y == other_y && x == other_x) { // 다른 공과 좌표가 같은 경우
		if (map[y][x] == 'O') return true; // 목적지인 경우에는 겹치기 허용
		else return false; // 목적지가 아니면 공끼리 겹치기 허용하지 않음
	}
	return true; // 벽, 공 겹치는 경우 외에는 이동 가능
}

ball move(ball obj, ball other, int d) {
	int ny, nx;
	while (1) {
		ny = obj.y + direction[d].first;
		nx = obj.x + direction[d].second;
		if (!isMovable(ny, nx, other.y, other.x)) break;
		if (map[ny][nx] == 'O') { // 목적지인 경우에는 이동하고 종료
			obj.y = ny; obj.x = nx;
			break;
		}
		obj.y = ny; obj.x = nx; // 이상 없으면 해당 좌표로 이동
	}
	return obj;
}

// 주어진 조건에 판을 기울여서 공을 움직인 뒤, 공의 이동한 좌표를 반환하는 함수
// 공의 좌표가 겹치는 경우는 오직 목적지에 도착했을 경우이다.
balls tilt(balls current, int direct) {
	balls next = current;
	if (direct == 0) { // 우측으로 기울이는 경우 (x++)
		if (current.red.x > current.blue.x) { // x가 더 큰 쪽이 먼저 움직여야 한다.
			next.red = move(current.red, current.blue, direct);
			next.blue = move(current.blue, next.red, direct);
		}
		else { // blue가 더 우측에 있는 경우, blue 먼저 이동
			next.blue = move(current.blue, current.red, direct);
			next.red = move(current.red, next.blue, direct);
		}
	} 
	else if (direct == 1) { // 아래로 기울이는 경우 (y++)
		if (current.red.y > current.blue.y) { // y가 더 큰 쪽이 먼저 움직여야 한다.
			next.red = move(current.red, current.blue, direct);
			next.blue = move(current.blue, next.red, direct);
		}
		else { // blue가 더 하단에 있는 경우, blue 먼저 이동
			next.blue = move(current.blue, current.red, direct);
			next.red = move(current.red, next.blue, direct);
		}
	}
	else if (direct == 2) { // 좌측으로 기울이는 경우 (x--)
		if (current.red.x < current.blue.x) { // x가 더 작은 쪽이 먼저 움직여야 한다.
			next.red = move(current.red, current.blue, direct);
			next.blue = move(current.blue, next.red, direct);
		}
		else { // blue가 더 좌측에 있는 경우, blue 먼저 이동
			next.blue = move(current.blue, current.red, direct);
			next.red = move(current.red, next.blue, direct);
		}
	}
	else if (direct == 3) { // 상단으로 기울이는 경우 (y--)
		if (current.red.y < current.blue.y) { // y가 더 작은 쪽이 먼저 움직여야 한다.
			next.red = move(current.red, current.blue, direct);
			next.blue = move(current.blue, next.red, direct);
		}
		else { // blue가 더 좌측에 있는 경우, blue 먼저 이동
			next.blue = move(current.blue, current.red, direct);
			next.red = move(current.red, next.blue, direct);
		}
	}
	return next; // 이동한 좌표를 반환한다.
}

int bfs() {
	queue<balls> q;
	q.push({ red, blue, 1 });
	visit[red.y][red.x][blue.y][blue.x] = 1;

	bool break_flag = false;
	int level_size, ret = INF;
	balls current, next;
	while (!q.empty()) {
		level_size = q.size();
		while (level_size--) {
			current = q.front(); q.pop();
			if (current.count > 10) {
				break_flag = true;
				break;
			}
			for (int direct = 0; direct < 4; ++direct) {
				next = tilt(current, direct);
				if (map[next.red.y][next.red.x] == 'O') { // red가 빠져나갔다면
					if (map[next.blue.y][next.blue.x] == 'O') { // blue도 빠져나갔다면
						visit[next.red.y][next.red.x][next.blue.y][next.blue.x] = 1;
						continue; // 다른 방향으로 기울여본다.
					}
					else { // red만 빠져나갔다면
						ret = min(ret, current.count); // 최소값 갱신
					}
				}
				else if (map[next.blue.y][next.blue.x] == 'O') { // blue만 빠져나갔다면
					visit[next.red.y][next.red.x][next.blue.y][next.blue.x] = 1;
					continue; // 다른 방향으로 기울여본다.
				}
				else if (!visit[next.red.y][next.red.x][next.blue.y][next.blue.x]) {
					++next.count;
					q.push(next);
					visit[next.red.y][next.red.x][next.blue.y][next.blue.x] = 1;
				}
			}
		}
		if (break_flag) break;
	}
	if (ret == INF) return -1;
	else return ret;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	input();
	cout << bfs();
	return 0;
}

개발 환경 : VS2019

질문, 지적 환영합니다!

'알고리즘 > 백준' 카테고리의 다른 글

[C++] 백준 1520 내리막길 (0)	2020.05.26
[C++] 백준 5373 큐빙 (0)	2020.05.26
[C++] 백준 15684 사다리 조작 (0)	2020.05.25
[C++] 백준 14891 톱니바퀴 (0)	2020.05.25
[C++} 백준 14890 경사로 (0)	2020.05.25

상경한 개발자 지망생들