[C++] G1 백준 13460 - 구슬탈출2(클래스5)

1. 문제 링크

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

소요 시간 : 2시간 19분

시도 횟수 : 2

 

2. 문제 설명

난이도 : G1

사용 알고리즘 : 구현(시뮬레이션), BFS

보드에서 빨간 구슬만 탈출시키기 위한 최소 동작 횟수를 알아내는 문제

 

3. 풀이 방식 및 해결

문제를 처음 읽어보는데 느껴지는 구현의 스멜

머릿속으로 보드를 이리저리 기울여가며 대충 움직임을 파악해봤다. 생각보다는 변수가 많지 않은 듯?

근데 최소 횟수를 구하라길래 BFS인가..?싶었다. DP도 생각을 해봤으나 음 어떻게 해야 할 지 잘 모르겠고,,

우선 BFS + 구현이라 생각하고 풀었는데 다행히 맞았다.

 

bool 배열로 각 칸이 장애물인지를 저장했고,
움직이는 방향마다 파랑과 빨강 구슬의 위치를 비교하여 어떤 구슬이 먼저 움직일지 정했다.
먼저 움직인 구슬의 위치를 장애물이 있다고 설정하고, 다음 구슬을 움직였다.
움직이는 과정에서 구멍을 지나는지 확인하고,
두 구슬이 움직이고 나서 장애물 설정을 되돌리기 !

장애물 설정을 되돌리는 코드를 넣어주지 않았어서 반복문을 도는 과정에 서로 다른 경우끼리 영향을 주었다.

해당 문제를 수정하니 문제가 해결되었따.

 

#include<iostream>
#include<string>
#include<queue>

using namespace std;

int n, m;
int r_y, r_x, b_y, b_x, o_y, o_x;
bool wall[11][11];
bool isvisit[101][101];//파랑, 빨강의 위치를 기준으로 재확인 방지
bool b_in = false, r_in = false;//구멍 통과 여부

int dx[4] = { 1,0,-1,0 };//오른쪽 아래 왼쪽 위
int dy[4] = { 0,1,0,-1 };

struct STATE {
	int r_y;
	int r_x;
	int b_y;
	int b_x;
	int cnt;
};

int loc(int y, int x) {//좌표를 pair 대신 숫자로 변환해서 저장
	return (y - 1) * m + x;
}

bool move(int* y, int* x, int i) {
	while (!wall[*y + dy[i]][*x + dx[i]]) {
		*y += dy[i];
		*x += dx[i];
		if (*y == o_y && *x == o_x) return true;
	}
	wall[*y][*x] = true;
	return false;
}

int bfs() {
	queue<STATE> q;
	int r = loc(r_y, r_x);
	int b = loc(b_y, b_x);
	isvisit[r][b] = true;
	q.push({ r_y, r_x, b_y, b_x, 0 });
	while (!q.empty()) {
		STATE tmp = q.front();
		q.pop();
		isvisit[loc(tmp.r_y, tmp.r_x)][loc(tmp.b_y, tmp.b_x)] = true;
		for (int i = 0; i < 4; i++) {
			STATE tmp2 = tmp;
			int& tmpbx = tmp2.b_x;
			int& tmpby = tmp2.b_y;
			int& tmprx = tmp2.r_x;
			int& tmpry = tmp2.r_y;
			if (i == 0) {//오른쪽
				if (tmpbx > tmprx) {
					b_in = move(&tmpby, &tmpbx, i);
					r_in = move(&tmpry, &tmprx, i);
				}
				else {
					r_in = move(&tmpry, &tmprx, i);
					b_in = move(&tmpby, &tmpbx, i);
				}
			}
			else if (i == 1) {//아래
				if (tmpby > tmpry) {
					b_in = move(&tmpby, &tmpbx, i);
					r_in = move(&tmpry, &tmprx, i);
				}
				else {
					r_in = move(&tmpry, &tmprx, i);
					b_in = move(&tmpby, &tmpbx, i);
				}
			}
			else if (i == 2) {//왼쪽
				if (tmpbx < tmprx) {
					b_in = move(&tmpby, &tmpbx, i);
					r_in = move(&tmpry, &tmprx, i);
				}
				else {
					r_in = move(&tmpry, &tmprx, i);
					b_in = move(&tmpby, &tmpbx, i);
				}
			}
			else {//위
				if (tmpby < tmpry) {
					b_in = move(&tmpby, &tmpbx, i);
					r_in = move(&tmpry, &tmprx, i);
				}
				else {
					r_in = move(&tmpry, &tmprx, i);
					b_in = move(&tmpby, &tmpbx, i);
				}
			}
			wall[tmp2.b_y][tmp2.b_x] = false;
			wall[tmp2.r_y][tmp2.r_x] = false;
			if (b_in) continue;
			if (r_in) return tmp.cnt + 1;
			tmp2.cnt++;
			int rr = loc(tmp2.r_y, tmp2.r_x);
			int bb = loc(tmp2.b_y, tmp2.b_x);
			bool visited = isvisit[rr][bb];
			if (!visited && tmp2.cnt < 10) q.push({ tmp2 });
		}
	}
	return -1;
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		string s;
		cin >> s;
		for (int j = 1; j <= m; j++) {
			if (s[j - 1] == '#') wall[i][j] = true;
			else wall[i][j] = false;
			if (s[j - 1] == 'R') {
				r_y = i;
				r_x = j;
			}
			else if (s[j - 1] == 'B') {
				b_y = i;
				b_x = j;
			}
			else if (s[j - 1] == 'O') {
				o_y = i;
				o_x = j;
			}
		}
	}
	cout << bfs();
}

 

<오늘의 TMI>
홍대에 마포리움이라는 곳에 왔어용
여기 공부하기 좋음 !