[BAEKJOON] 13460번 구슬 탈출 2

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

13460번: 구슬 탈출 2

문제조건

1. N x M 크기의 보드가있다.
2. 빨간공과, 파란공이 각 하나씩 있다.(위치 주어짐)
3. 공을 내보낼수있는 구멍이 하나 있다.(위치 주어짐)
4. 보드를 왼쪽으로 기울이기, 오른쪽으로 기울이기, 위쪽으로 기울이기, 아래쪽으로 기울이기와 같은 네 가지 동작이 가능하다.
5. 이 동작만으로 공을 움직여서 빨간공만 구멍으로 빼야한다.
6. 빨간공, 파란공은 항상 같이 움직인다.
7. '#'은 공이 이동할수 없는 위치이다.
8. 만약, 10번 이하로 움직여서 빨간 구슬을 구멍을 통해 빼낼 수 없으면 -1을 출력한다.
9. 최소 몇 번 만에 빨간 구슬을 구멍을 통해 빼낼 수 있는지?

문제조건이 되게 까다로워서 국어 비문학 지문을 읽는줄 알았다,,,,아무튼 구현에 들어가지않고 계속해서 지문을 완전히 이해하는데만 20분 정도 걸린것같다.

사실 처음에 무작정 구현하다가 파란공생각안하고 틀린건 비밀

이 문제에서 핵심은 일반적인 BFS탐색이 아니라, 보드를 한번 기울였으면, 빨간공 파란공 둘다 '#'을 만날때 까지 한 방향으로 진행 한다는 점이다.

빨간공과 파란공이 이동했을때 동일 직선상에 없다면 아무문제 없이 진행되겠지만, 동일 직선상에 있는경우 한방향으로 이동했을때, 겹치는 경우가 발생한다.

나는 이러한 부분을 빨간공, 파란공 각각에 대해 이동한 거리를 기록해서 이동한 거리가 긴쪽이 다른 공에 막혀서 더 이동했다는 의미이므로, 진행하는 방향의 반대방향으로 한번 후퇴시켜줬다.

또한 몇번 움직였는지 알아야하므로, 한 방향으로 전부 탐색한뒤 구조체 큐 안에 cnt 카운트 개수를 저장했다.

 

• BFS이므로, 탐색하다가 'O'(구멍)이 나오면 당연히 최솟값인건 다들 알거라고 생각한다.

한마디로 이 문제를 정리하면, BFS를 기반으로한 빡구현이 되시겠다!

 

소스코드

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

int N, M, visited[11][11][11][11];
char map[11][11];
int dy[] = { -1, 0, 1, 0 };
int dx[] = { 0, -1, 0, 1 };

struct ball {
	int ry, rx;
	int by, bx;
	int cnt;
};

void move(int& ry, int& rx, int& dist, int& i) {
	// '#' 만날때 까지 한방향으로 탐색
	while (map[ry + dy[i]][rx + dx[i]] != '#' && map[ry][rx] != 'O') {
		ry += dy[i];
		rx += dx[i];
		dist++;
	}
}

void bfs(int ry, int rx, int by, int bx) {
	queue<ball> q;
	q.push({ry,rx,by,bx, 0});
	visited[ry][rx][by][bx] = 1;
	while (!q.empty()) {
		int ry = q.front().ry;
		int rx = q.front().rx;
		int by = q.front().by;
		int bx = q.front().bx;
		int cnt = q.front().cnt;
		q.pop();
		if (cnt >= 10) break;
		for (int i = 0; i < 4; i++) {
			int nry = ry;
			int nrx = rx;
			int nby = by;
			int nbx = bx;
			int rdist = 0, bdist = 0;
			int res = cnt + 1;
			//한 방향으로 한 칸씩 방문한다.
			move(nry, nrx, rdist, i);
			move(nby, nbx, bdist, i);
			if (map[nby][nbx] == 'O') continue;
			if(map[nry][nrx] == 'O'){
				cout << res;
				return;
			}	
			//빨강, 파랑 공 겹치는경우
			if (nry == nby && nrx == nbx) {
				if (rdist > bdist) {
					nry -= dy[i];
					nrx -= dx[i];
				}
				else {
					nby -= dy[i];
					nbx -= dx[i];
				}
			}
			if (visited[nry][nrx][nby][nbx]) continue;
			visited[nry][nrx][nby][nbx];
			//한방향에서 마지막지점 큐에 푸시
			q.push({ nry, nrx, nby, nbx, res });
		}
	}
	cout << -1;
}

int main(){
	cin >> N >> M;
	int rx = 0, ry = 0, by = 0, bx = 0;
	for (int i = 0; i < N; i++) {
		string m;
		cin >> m;
		for (int j = 0; j < M; j++) {
			map[i][j] = m[j];
			if (m[j] == 'R') {
				ry = i;
				rx = j;
			}
			else if (m[j] == 'B') {
				by = i;
				bx = j;
			}
		}
	}
	bfs(ry, rx, by, bx);
}

머리가 뜨끈뜨끈하다,,,,