백준 13459번 : 구슬 탈출 - BFS C++ 문제풀이코드

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

13459번: 구슬 탈출

1. 문제설명

구슬이 있는 판을 상하좌우로 기울일 수 있고,10번의 기회가 있다.

빨간색 구슬만 'O'를 만나는 경우가 있다면 1을 출력하고 없으면 0을 출력한다.

빨간색구슬이 'O'를 만날 때 파란색 구슬도 'O'를 만나는 경우는 제외한다.

 

2. 알고리즘

1. 구슬 판을 기울이는 함수를 구현해야 한다. dx, dy 방향으로 움직이고 'O'이나 '#'을 만나면 멈춘다.

2. 4방향으로 구슬판을 기울이고 기울인 결과가 이전에 이미 했던 경우가 아니라면 큐에 넣어준다.

3. 기울인 결과를 check 해주는 배열에 넣어준다.

4. BFS를 10번 돌 때 까지 빨간 공이 'O를 만나는 경우가 존재하지 않으면 BFS를 종료하고 '0'을 출력한다.

 

 

 

 

3.문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;
int n, m, red_x, red_y, blue_x, blue_y, cnt = 0;

char board[15][15];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
bool vis[15][15][15][15], isend;

struct Edge {
	//c는 BFS 시행 횟수 저장 
	int a, b, c;
	Edge(int x, int y, int z) {
		a = x;
		b = y;
		c = z;
	}

};

//끝까지 이동
void move(int &nrx, int &nry, int dx, int dy, int &rcnt) {
	while (1) {
		if (board[nrx][nry] == '#') { //벽에 무조건 걸린다
			nrx -= dx;
			nry -= dy;
			rcnt--;
			break;
		}
		if (board[nrx][nry] == 'O') {
			break;
		}
		nrx += dx;
		nry += dy;
		rcnt++;
	}
}

//
//void print(int nrx, int nry, int nbx, int nby, int count) {
//	cout << "----------------\n";
//
//	for (int i = 1; i <= n; i++) {
//		for (int j = 1; j <= m; j++) {
//			if (i == nrx && j == nry) cout << 'R';
//			else if (i == nbx && j == nby) cout << "B";
//			else cout << board[i][j];
//		}
//		cout << '\n';
//	}
//	cout << "BFS CNT : "<<count << "-------------\n\n";
//}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	//Red//Blue 순
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> board[i][j];
			if (board[i][j] == 'R') {
				board[i][j] = '.';
				red_x = i;
				red_y = j;
			}
			else if (board[i][j] == 'B') {
				board[i][j] = '.';
				blue_x = i;
				blue_y = j;
			}
		}
	}
	queue<Edge> Q;
	Q.push(Edge(red_x,red_y,0));
	Q.push(Edge(blue_x,blue_y,0));
	vis[red_x][red_y][blue_x][blue_y] = 1;

	while (!Q.empty()) {
		int rx = Q.front().a;
		int ry = Q.front().b;
		Q.pop();
		int bx = Q.front().a;
		int by = Q.front().b;
		int count = Q.front().c;
		Q.pop();


		//print(rx, ry, bx, by, count);
		if (count >= 10) break;
		

		for (int i = 0; i < 4; i++) {
			int rcnt = 0, bcnt = 0;
			int nrx = rx;
			int nry = ry;
			int nbx = bx;
			int nby = by;
			move(nrx, nry, dx[i], dy[i], rcnt);
			move(nbx, nby, dx[i], dy[i], bcnt);

			if (board[nbx][nby] == 'O') {
				continue;
			}
			else if (board[nrx][nry] == 'O') {
				//print(nrx, nry, nbx, nby, count + 1);
				cout << 1 << '\n';
				isend = true;
				return 0;
			}
			else {
				if (nbx == nrx && nry == nby) {
					if (rcnt > bcnt) {
						nrx -= dx[i];
						nry -= dy[i];
					}
					else {
						nbx -= dx[i];
						nby -= dy[i];
					}
				}
				if (vis[nrx][nry][nbx][nby] == 0) {
					vis[nrx][nry][nbx][nby] = 1;
					Q.push(Edge(nrx,nry,count+1));
					Q.push(Edge(nbx,nby,count+1));
				}
			}
		}
	}

	if (!isend) {
		cout << 0;
	}
	return 0;
}

백준 13459번 구슬탈출 

 

주석 부분을 해제하면 이동 과정을 출력해볼 수 있다.

 

문제푸는데 헷갈려서 넣어봤다.

 

구슬 이동 출력

백준 13459번 구슬탈출 구슬이동과정

백준 13459번 구슬탈출 구슬이동과정

 

 

문제풀이후기

아무래도 그동안 풀던 문제에 비해 코드 길이는 길어졌다.

코드를 함수를 잘 만들어서 중복되는 부분을 줄일수록 코드 구성을 판단하기 쉬워진다.

복잡하지만 결국 4방향에 대해 너비우선탐색을 하여

문제조건에 알맞는 결과가 있다면 종료해주는 문제였다.

다만 탐색하는 부분에 대하여 조건에 맞춰 코드를 작성해야할 필요가 있다.