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

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

13460번: 구슬 탈출 2

엄청나게.... 빡취는 문제

 

구슬이 들어있는 판을 이리저리 굴려서(이동이 멈출때까지 방향 전환X) 10회 안에 구멍에 빨간 구슬만 들어갈 수 있나?

라는 문제당

예제입력 2번

예제 2번은 위와 같이 5번의 이동만에 구멍에 도달할 수 있다

디버깅 하기 까다로운 BFS+완탐 조건 때문에 애를 먹을 수 있다 ^^

 

나는 일단 (좌표, 이동 횟수, 이전 이동 방향)을 큐에 담아 BFS로 돌렸고, 구멍에 도달한 지점에서의 이동 횟수가 최솟값이라면 최솟값을 계속해서 갱신해주었다.

그리고 이전에 이동했던 방향 및 반대 방향은 루프에서 제외했다.

(예시: 오왼(이동한 의미가 없음), 오오(두번째 이동은 움직이지 않음))

 

구슬의 이동 함수에서는 이동 방향 쪽에 치우쳐있는 구슬을 먼저 이동시켜주도록 순서를 정했다

(위의 예제입력 2번에서 왼쪽으로 이동할 때는 왼쪽에 있는 빨간 구슬 부터 이동)

두 구슬 모두 빈칸을 계속 이동해주도록 하고나서

 

1. 파란 구슬이 구멍에 들어갔는가?     ->    실패. 초기 좌표 반환

2. 빨간 구슬이 구멍에 들어갔는가?     ->    성공을 의미하는 0,0,0,0 좌표 반환

3. 2번과 동시에 파란 구슬이 구멍에 들어갔는가?     -> 1번과 같이 초기 좌표 반환

4. 123 전부 아니다    ->    일반 이동. 이동한 좌표 반환

 

를 체크해주니 성공했다.

 

#include <cstdio>
#include <queue>
#define pii pair<int,int>
#define x first
#define y second
using namespace std;
int n, m, ans = 987654321, dx[] = { 1,0,-1,0 }, dy[] = { 0,1,0,-1 };
char s[12][12];
typedef struct {
	int rx, ry;
	int bx, by;
}point;
typedef struct {
	point p;
	int dep, dir;
}ball;
queue<ball> q;
point move(point a, int d) {
	pii red = { a.rx,a.ry }, blue = { a.bx,a.by };
	bool check = false;
	if ((d == 0 && (red.x > blue.x))
		|| (d == 1 && (red.y > blue.y))
		|| (d == 2 && (red.x < blue.x))
		|| (d == 3 && (red.y < blue.y))
		)check = 1;

	while (s[red.y + dy[d]][red.x + dx[d]] == '.' && check) {	//빨강먼저
		red.x += dx[d];
		red.y += dy[d];
	}
	while (s[blue.y + dy[d]][blue.x + dx[d]] == '.'
		&& !(blue.y+dy[d]==red.y && blue.x+dx[d]==red.x)) {
		blue.x += dx[d];
		blue.y += dy[d];
	}
	while (s[red.y + dy[d]][red.x + dx[d]] == '.' && !check
		&& !(red.y + dy[d] == blue.y && red.x + dx[d] == blue.x)) {	//파랑먼저
		red.x += dx[d];
		red.y += dy[d];
	}

	if (s[blue.y + dy[d]][blue.x + dx[d]] == 'O')return a;
	else if (s[red.y + dy[d]][red.x + dx[d]] == 'O') {
		if (blue.y + dy[d] == red.y && blue.x + dx[d] == red.x)	//둘다 구슬에 빠지면
			return a;
		return { 0,0,0,0 };
	}
	else
		return a = { red.x,red.y,blue.x,blue.y };
}

int main() {
	point fst = { 0,0,0,0 };
	scanf("%d%d ", &n, &m);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf("%c", &s[i][j]);
			if (s[i][j] == 'R') { fst.rx = j; fst.ry = i; s[i][j] = '.'; }
			if (s[i][j] == 'B') { fst.bx = j; fst.by = i; s[i][j] = '.'; }
		}
		scanf(" ");
	}

	q.push({ fst,0,0 });
	while (!q.empty()) {
		point cur = q.front().p, next;
		int dep = q.front().dep+1, dir=q.front().dir;
		q.pop();
		if (dep > ans||dep>10)continue;
		for (int i = 0; i < 4; i++) {
			if (dep>1&&(dir == i || (dir + 2) % 4 == i))continue;
			next = move(cur, i);
			if (!next.rx && !next.ry && !next.bx && !next.by)
				ans = dep < ans ? dep : ans;
			else if ((next.rx == cur.rx)
				&& (next.ry == cur.ry)
				&& (next.bx == cur.bx)
				&& (next.by == cur.by))continue;
			else {
				q.push({ next,dep,i });
			}
		}
	}

	printf("%d", ans== 987654321?-1:ans);
	return 0;
}

 

 

+ 반례 모음👇👇

6 8
########
#R....B#
##.#####
#......#
#.O....#
########
답 :: -1

5 8
########
#RB.##.#
##.#####
#.O..###
########
답 :: 2

6 7
#######
#..BR##
#.#####
#.#O###
#....##
#######
답 :: 8

6 7
#######
##RB..#
#####.#
###O#.#
##....#
#######
답 :: 8

6 7
#######
#..BR##
#.#####
#.#O###
#....##
#######
답 :: 8

6 7
#######
#....##
#.#O###
#.#####
#..BR##
#######
답 :: 8

6 7
#######
##....#
###O#.#
#####.#
##RB..#
#######
답 :: 8

5 10 
##########
#........#
#.####...#
#R##O..#B#
##########
답 :: 6

6 3
###
#O#
#.#
#B#
#R#
###
답 :: -1

9 10
##########
#B......R# 
##.O.....#
##.####..#
##.####..#
##.####..#
##.####..#
##.......#
##########
답 :: 4

 

5 5
#####
#B..#
#.R.#
#O.##
#####
correct answer: -1

5 4
####
##B#
#R.#
#.O#
####
correct answer: -1

5 4
####
#.##
#BR#
#O.#
####
correct answer: -1