[G1] 백준 13459번 구슬 탈출 C++ 구현, 시뮬레이션, 너비 우선 탐색

알고리즘 공부/C++

[G1] 백준 13459번 구슬 탈출 C++ 구현, 시뮬레이션, 너비 우선 탐색

마달랭 2025. 1. 23. 11:07

리뷰

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

오랜만에 풀어본 진또배기 구현 및 시뮬레이션 문제, 코드 길이만 282줄이다.

이 문제는 유사 문제가 존재한다.

[G1] 백준 13460번 구슬 탈출 2 C++ BFS, 구현, 시뮬레이션, 너비 우선 탐색

리뷰 설계를 하지 않고 무작정 덤볐다가 호되게 당한 문제, 구현과 시뮬레이션은 둘째치고 생각 못하고 있던 조건들이 많아서 애를 먹었다, 해당 문제를 풀기 전에 문제에 대한 조건을 한번 쭉

zzzz955.tistory.com

전역 변수

n : 맵의 세로 길이를 저장할 변수
m : 맵의 가로 길이를 저장할 변수
lst : 맵 정보를 저장하기 위한 문자열 배열
v : 방문 정보를 체크하기 위한 논리형 4차 배열
dx, dy : 4방향 탐색을 위한 방향 배열
Pos : 파란 구슬의 위치 bx, by, 빨간 구슬의 위치 rx, ry, 소요 시간 t를 정의한 구조체
start : 구슬의 초기 위치를 저장할 Pos타입의 변수

함수

1. input

void input()

맵 정보를 입력받아 초기 구슬 정보를 저장하기 위한 함수

n, m값을 입력 받고 n * m크기의 맵 정보를 입력 받아준다.
'B'가 입력되면 start의 bx, by에 위치값을 저장하고 맵에서 빈 공간으로 만들어 준다.
'R'이 입력되면 start의 rx, ry에 위치값을 저장하고 맵에서 빈 공간으로 만들어 준다.

2. bfs

int bfs()

너비 우선 탐색을 통해 10턴 내로 빨간 구슬만 탈출 가능한지 여부를 시뮬레이션 하는 함수

Pos타입의 큐 q를 초기화 하고 start를 push해준다.
v배열에 초기 구슬의 위치 정보를 방문처리 해준다.
q가 빌 때 까지 while루프를 수행하고, 매 루프마다 요소를 한개씩 꺼내어 준다.
기저 조건으로 소요 시간이 10일 경우 continue처리해 준다.
4방향 탐색을 시작하고 각 이동 방향에 따라 if문을 나누어 준다.
공통적으로 bf, rf를 가지며 이는 각 색의 구슬이 탈출했는지 여부를 나타낸다.
각 방향으로 벽을 만나거나 다른 구슬을 만나기 전 까지 이동을 진행해 준다.
이 때 각 이동할 방향에 따라 앞쪽에 있는 구슬을 먼저 이동시켜 준다.
만약 탈출구를 만난 경우 bf혹은 rf를 true로 처리해 주고, 구슬의 위치를 맵 밖으로 이동시켜 준 후 break한다.
최종적으로 해당 방향으로 끝까지 이동한 위치가 방문처리 되어 있다면 continue해준다.
방문처리 되어 있지 않다면 방문처리 후 q에 push해준다.
만약 while 루프가 끝날 때 까지 기저 조건에 도달하지 못했다면 0을 리턴해 준다.

3. print

void print(int bx, int by, int rx, int ry)

소요 시간에 따라 구슬의 위치를 디버깅 하기 위한 함수

매개 변수로 파란 구슬의 위치 bx, by와 빨간 구슬의 위치 rx, ry를 입력 받는다.
현재 각 구슬의 위치를 출력을 해주고, 실제 맵에서 어디 있는지 출력을 해준다.

문제풀이

input함수를 호출하여 맵과 초기 구슬의 정보를 초기화 해준다.
bfs함수를 호출하고 받은 리턴값을 출력해 준다.

트러블 슈팅

예제 7번의 결과가 1이 나와서 이미 탈출한 구슬의 위치를 맵 밖으로 이동하도록 로직을 수정해 주었다.

참고 사항

각 이동 로직에서 while의 조건에 벗어나 루프를 빠져나온 경우 각 방향만큼 한번씩 빼주어야 한다.
그렇지 않으면 맵을 벗어나거나 구슬끼리 겹치는 현상을 볼 수 있다.

정답 코드

#include<iostream>
#include<queue>
using namespace std;

int n, m;
string lst[10];
bool v[10][10][10][10];
int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };
struct Pos {
	int bx, by, rx, ry, t;
};
Pos start;

void print(int bx, int by, int rx, int ry) {
	cout << bx<< " " << by << " " << rx << " " << ry << "\n";
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			if (bx == i && by == j) cout << "B";
			else if (rx == i && ry == j) cout << "R";
			else cout << lst[i][j];
		}
		cout << "\n";
	}
}

int bfs() {
	queue<Pos> q;
	q.push(start);
	v[start.bx][start.by][start.rx][start.ry] = 1;

	while (!q.empty()) {
		Pos pos = q.front(); q.pop();
		int cbx = pos.bx, cby = pos.by, crx = pos.rx, cry = pos.ry, ct = pos.t;
		if (ct == 10) continue;

		for (int i = 0; i < 4;++i) {
			if (i == 0) {
				bool bf = false, rf = false;
				int nbx = cbx + dx[i], nrx = crx + dx[i];
				if (nbx > nrx) {
					while (lst[nbx][cby] != '#') {
						if (lst[nbx][cby] == 'O') {
							bf = true;
							nbx = -1;
							break;
						}
						nbx += dx[i];
					}
					nbx -= dx[i];

					while (lst[nrx][cry] != '#' && (nrx != nbx || cby != cry)) {
						if (lst[nrx][cry] == 'O') {
							rf = true;
							nrx = -1;
							break;
						}
						nrx += dx[i];
					}
					nrx -= dx[i];
				}
				else {
					while (lst[nrx][cry] != '#') {
						if (lst[nrx][cry] == 'O') {
							rf = true;
							nrx = -1;
							break;
						}
						nrx += dx[i];
					}
					nrx -= dx[i];

					while (lst[nbx][cby] != '#' && (nrx != nbx || cby != cry)) {
						if (lst[nbx][cby] == 'O') {
							bf = true;
							nbx = -1;
							break;
						}
						nbx += dx[i];
					}
					nbx -= dx[i];
				}

				if (bf) continue;
				else if (rf) return 1;

				if (v[nbx][cby][nrx][cry]) continue;
				v[nbx][cby][nrx][cry] = true;
				q.push({ nbx, cby, nrx, cry, ct + 1 });
				//print(nbx, cby, nrx, cry);
			}
			else if (i == 1) {
				bool bf = false, rf = false;
				int nbx = cbx + dx[i], nrx = crx + dx[i];
				if (nbx <= nrx) {
					while (lst[nbx][cby] != '#') {
						if (lst[nbx][cby] == 'O') {
							bf = true;
							nbx = -1;
							break;
						}
						nbx += dx[i];
					}
					nbx -= dx[i];

					while (lst[nrx][cry] != '#' && (nrx != nbx || cby != cry)) {
						if (lst[nrx][cry] == 'O') {
							rf = true;
							nrx = -1;
							break;
						}
						nrx += dx[i];
					}
					nrx -= dx[i];
				}
				else {
					while (lst[nrx][cry] != '#') {
						if (lst[nrx][cry] == 'O') {
							rf = true;
							nrx = -1;
							break;
						}
						nrx += dx[i];
					}
					nrx -= dx[i];

					while (lst[nbx][cby] != '#' && (nrx != nbx || cby != cry)) {
						if (lst[nbx][cby] == 'O') {
							bf = true;
							nbx = -1;
							break;
						}
						nbx += dx[i];
					}
					nbx -= dx[i];
				}

				if (bf) continue;
				else if (rf) return 1;

				if (v[nbx][cby][nrx][cry]) continue;
				v[nbx][cby][nrx][cry] = true;
				q.push({ nbx, cby, nrx, cry, ct + 1 });
				//print(nbx, cby, nrx, cry);
			}
			else if (i == 2) {
				bool bf = false, rf = false;
				int nby = cby + dy[i], nry = cry + dy[i];
				if (nby > nry) {
					while (lst[cbx][nby] != '#') {
						if (lst[cbx][nby] == 'O') {
							bf = true;
							nby = -1;
							break;
						}
						nby += dy[i];
					}
					nby -= dy[i];

					while (lst[crx][nry] != '#' && (nry != nby || cbx != crx)) {
						if (lst[crx][nry] == 'O') {
							rf = true;
							nry = -1;
							break;
						}
						nry += dy[i];
					}
					nry -= dy[i];
				}
				else {
					while (lst[crx][nry] != '#') {
						if (lst[crx][nry] == 'O') {
							rf = true;
							nry = -1;
							break;
						}
						nry += dy[i];
					}
					nry -= dy[i];

					while (lst[cbx][nby] != '#' && (crx != cbx || nby != nry)) {
						if (lst[cbx][nby] == 'O') {
							bf = true;
							nby = -1;
							break;
						}
						nby += dy[i];
					}
					nby -= dy[i];
				}

				if (bf) continue;
				else if (rf) return 1;

				if (v[cbx][nby][crx][nry]) continue;
				v[cbx][nby][crx][nry] = true;
				q.push({ cbx, nby, crx, nry, ct + 1 });
				//print(cbx, nby, crx, nry);
			}
			else if (i == 3) {
				bool bf = false, rf = false;
				int nby = cby + dy[i], nry = cry + dy[i];
				if (nby <= nry) {
					while (lst[cbx][nby] != '#') {
						if (lst[cbx][nby] == 'O') {
							bf = true;
							nby = -1;
							break;
						}
						nby += dy[i];
					}
					nby -= dy[i];

					while (lst[crx][nry] != '#' && (nry != nby || cbx != crx)) {
						if (lst[crx][nry] == 'O') {
							rf = true;
							nry = -1;
							break;
						}
						nry += dy[i];
					}
					nry -= dy[i];
				}
				else {
					while (lst[crx][nry] != '#') {
						if (lst[crx][nry] == 'O') {
							rf = true;
							nry = -1;
							break;
						}
						nry += dy[i];
					}
					nry -= dy[i];

					while (lst[cbx][nby] != '#' && (crx != cbx || nby != nry)) {
						if (lst[cbx][nby] == 'O') {
							bf = true;
							nby = -1;
							break;
						}
						nby += dy[i];
					}
					nby -= dy[i];
				}

				if (bf) continue;
				else if (rf) return 1;

				if (v[cbx][nby][crx][nry]) continue;
				v[cbx][nby][crx][nry] = true;
				q.push({ cbx, nby, crx, nry, ct + 1 });
				//print(cbx, nby, crx, nry);
			}
		}
	}
	return 0;
}

void input() {
	cin >> n >> m;
	for (int i = 0; i < n; ++i) {
		cin >> lst[i];
		for (int j = 0; j < m; ++j) {
			if (lst[i][j] == 'B') {
				start.bx = i, start.by = j;
				lst[i][j] = '.';
			}
			else if (lst[i][j] == 'R') {
				start.rx = i, start.ry = j;
				lst[i][j] = '.';
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	input();
	cout << bfs();
}

728x90

'알고리즘 공부 > C++' 카테고리의 다른 글

[G1] 백준 17143번 낚시왕 C++ 구현, 시뮬레이션, 우선순위 큐 (0)	2025.01.22
[G1] 백준 11689번 GCD(n, k) = 1 C++ 정수론, 오일러 피 함수 (0)	2025.01.21
[P4] 백준 5670번 휴대폰 자판 C++ 트라이, 메모리 풀 (0)	2025.01.20
[S1] 백준 2468번 안전 영역 C++ 너비 우선 탐색, 플러드 필 (0)	2025.01.20
[P5] 백준 15678번 연세워터파크 C++ 덱, 덱을 이용한 다이나믹 프로그래밍 (0)	2025.01.19

현재글[G1] 백준 13459번 구슬 탈출 C++ 구현, 시뮬레이션, 너비 우선 탐색

개인사

개발이 인생인 사람

250x250

C++, 자료 구조, 파이썬, SWEA, 백준, 프로그래머스, Boost, 완전 탐색, 트리, 구현, 세그먼트 트리, 시뮬레이션, 너비 우선 탐색, 백트래킹, 다익스트라, dfs, 브루트포스 알고리즘, boost.asio, 리눅스, BFS,

Today :
Yesterday :

개인사