[백준] 13460번: 구슬 탈출 2

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

13460번: 구슬 탈출 2

문제 이해

파랑 구슬과 빨강 구슬이 한꺼번에 움직이는 동작을 구현하는 게 어렵다.

최소 횟수를 구하는 거니까 BFS를 이용하면 되는데, 한 칸 움직이는 게 아니라 쏠리는 거라서 조금 까다로웠다. 

 

BFS()

일단 BFS부터 설명하자면 파란구슬의 좌표, 빨간 구슬의 좌표를 큐에 넣어준다.

visited배열은 4차원으로 (파란 구슬 좌표 + 빨간 구슬 좌표) 그 상태를 이미 탐색했는지 표시한다.

 

모든 경우를 탐색하면 된다.

방향을 정해서 파란 구슬과 빨간 구슬의 좌표를 옮겨본다. (Move_Marble())

파란 구슬이 구멍으로 들어가면 이 경우는 무시해버린다. (여기서 더 나아가지 않도록 continue)

빨간 구슬이 구멍으로 들어간 경우면 성공했으니까 그때까지 걸린 시간을 리턴해주면 된다.

 

10번 이상 움직했다면 더이상 가지 않는다. 그 경우는 실패라고 간주할 것이기 때문이다.

int BFS(void) {

	enq(BY, BX, RY, RX, 0);
	visited[BY][BX][RY][RX] = 1;

	while (!empty()) {
		ELE cur = deq();
		if (cur.cnt >= 10) continue; // '>'이면 return cur.cnt+1 == 11이 갈 수 있다!!
		for (int i = 0; i < 4; i++) {
			Move_Marble(cur.by, cur.bx, cur.ry, cur.rx, i);
			if (visited[nby][nbx][nry][nrx] == 1) continue;
			if (map[nby][nbx] == 'O') continue; // 파란 구슬이 빠졌다 -> 이 경우 안됨
			if (map[nry][nrx] == 'O') {
				// 빨간 구슬 도착
				return cur.cnt + 1;
			}
			enq(nby, nbx, nry, nrx, cur.cnt + 1);
			visited[nby][nbx][nry][nrx] = 1;
		}
	}
	return -1;
}

 

Move_Marble()

그냥 빨간 구슬이나 파란 구슬이나 벽이 있을 때까지 그 방향으로 옮겨주면 되는데

고민되는 부분이 예제2와 같은 경우였다.

그냥 단순하게 R도 벽까지, B도 벽까지 보내면 좌표가 둘이 겹쳐버리기 때문이다.

그래서 그렇게 옮긴 후에, 처음 R, B의 상대적 위치에 따라서 둘 중 하나를 전 위치로 바꿔주는 식으로 구현했다.

void Move_Marble(int by, int bx, int ry, int rx, int i) {
	nby = by, nbx = bx;
	nry = ry, nrx = rx;
	while (1) { // 파란 구슬 최대 이동
		nby += dy[i], nbx += dx[i];
		if (map[nby][nbx] == '#') {
			nby -= dy[i], nbx -= dx[i];
			break;
		}
		if (map[nby][nbx] == 'O') {
			return;
		}
	}
	while (1) { // 빨간 구슬 최대 이동
		nry += dy[i], nrx += dx[i];
		if (map[nry][nrx] == '#') {
			nry -= dy[i], nrx -= dx[i];
			break;
		}if (map[nry][nrx] == 'O') {
			return;
		}
	}
	if (nby == nry && nbx == nrx) { // 이동 후 둘의 위치가 같다면
		if (i == 0) { // 동
			if (bx < rx) nbx -= dx[i]; // rx가 더 동쪽에 있었음
			else nrx -= dx[i];
		} 
		else if (i == 1) { // 서
			if (bx < rx) nrx -= dx[i]; // bx가 더 서쪽에 있었음
			else nbx -= dx[i];
		}
		else if (i == 2) { // 남
			if (by < ry) nby -= dy[i]; //ry가 더 밑에 있었음
			else nry -= dy[i];
		}
		else { //북
			if (by < ry) nry -= dy[i];// by가 더 위에 있었음
			else nby -= dy[i];
		}
	}
}

 

최종 코드

#include <stdio.h>
#include <string.h>
#define MAXNM 10

int N, M;
char map[MAXNM+5][MAXNM+5];
int visited[MAXNM+5][MAXNM+5][MAXNM + 5][MAXNM + 5];
int BY, BX, RY, RX;
int nby, nbx, nry, nrx;

int dy[] = { 0, 0, 1, -1 }; // 동서남북
int dx[] = { 1, -1, 0, 0 };

typedef struct st {
	int by, bx, ry, rx, cnt;
}ELE;
ELE q[MAXNM * MAXNM * MAXNM * MAXNM * 10];
int wp, rp;
void enq(int by, int bx, int ry, int rx, int cnt) {
	q[wp].by = by, q[wp].bx = bx;
	q[wp].ry = ry, q[wp].rx = rx;
	q[wp++].cnt = cnt;
}
ELE deq(void) { return q[rp++]; }
int empty(void) { return wp == rp; }


void Get_Input(void) {
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++) {
		scanf("%s", &map[i]);
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (map[i][j] == 'B') BY = i, BX = j;
			if (map[i][j] == 'R') RY = i, RX = j;
		}
	}
}

void Move_Marble(int by, int bx, int ry, int rx, int i) {
	nby = by, nbx = bx;
	nry = ry, nrx = rx;
	while (1) { // 파란 구슬 최대 이동
		nby += dy[i], nbx += dx[i];
		if (map[nby][nbx] == '#') {
			nby -= dy[i], nbx -= dx[i];
			break;
		}
		if (map[nby][nbx] == 'O') {
			return;
		}
	}
	while (1) { // 빨간 구슬 최대 이동
		nry += dy[i], nrx += dx[i];
		if (map[nry][nrx] == '#') {
			nry -= dy[i], nrx -= dx[i];
			break;
		}if (map[nry][nrx] == 'O') {
			return;
		}
	}
	if (nby == nry && nbx == nrx) { // 이동 후 둘의 위치가 같다면
		if (i == 0) { // 동
			if (bx < rx) nbx -= dx[i]; // rx가 더 동쪽에 있었음
			else nrx -= dx[i];
		} 
		else if (i == 1) { // 서
			if (bx < rx) nrx -= dx[i]; // bx가 더 서쪽에 있었음
			else nbx -= dx[i];
		}
		else if (i == 2) { // 남
			if (by < ry) nby -= dy[i]; //ry가 더 밑에 있었음
			else nry -= dy[i];
		}
		else { //북
			if (by < ry) nry -= dy[i];// by가 더 위에 있었음
			else nby -= dy[i];
		}
	}
}

int BFS(void) {

	enq(BY, BX, RY, RX, 0);
	visited[BY][BX][RY][RX] = 1;

	while (!empty()) {
		ELE cur = deq();
		if (cur.cnt >= 10) continue; // '>'이면 return cur.cnt+1 == 11이 갈 수 있다!!
		for (int i = 0; i < 4; i++) {
			Move_Marble(cur.by, cur.bx, cur.ry, cur.rx, i);
			if (visited[nby][nbx][nry][nrx] == 1) continue;
			if (map[nby][nbx] == 'O') continue; // 파란 구슬이 빠졌다 -> 이 경우 안됨
			if (map[nry][nrx] == 'O') {
				// 빨간 구슬 도착
				return cur.cnt + 1;
			}
			enq(nby, nbx, nry, nrx, cur.cnt + 1);
			visited[nby][nbx][nry][nrx] = 1;
		}
	}
	return -1;
}

int main(void) {
	Get_Input();
	int res = BFS();
	printf("%d", res);
	return 0;
}