[BOJ]백준 13460번: 구슬 탈출2 풀이 및 코드

www.acmicpc.net/problem/13460

13460번: 구슬 탈출 2

한 번 꼬이면 답없는 구슬탈출 문제 ‼⁉❓💯⁉‼

항상 중요한 것은 문제에 언급한 조건과 순서를 정확히 지켰는지 !! 확인하는 것 !!!

나는 백트래킹, dfs를 이용해서 풀어줬당

① 현재 좌표를 미리 저장해둔다

② 이동하려고 하는 방향에 어떤 구슬이 앞서는지 체크 !! (ex. 오른쪽으로 이동하려고 할 때 파란색의 x좌표가 더 크다면 파란색부터 이동시켜준다)

③ 구슬들을 차례로 이동해준 뒤 파랑 or 빨강이 구멍에 빠졌는지 체크해준다

④ 파랑이 빠졌거나 / 구슬에 움직임이 없을 경우에는 pass해준다

⑤ 빨강만 빠졌다면 answer를 업데이트 해준다

⑥ 4, 5번 둘다에 해당이 되지 않는다면 (이동해준 좌표 그대로 두고) 재귀함수를 호출

⑦ 1번에 저장해뒀던 좌표로 다시 돌려준다

 

#include <cstdio>
typedef struct { int x, y; }point;
int ans = 11, n, m,dx[] = { 1,0,-1,0 }, dy[] = { 0,1,0,-1 };
char s[13][13];
point red, blue;
bool cmp(int dir) {
	switch (dir) {
	case 0:
		return red.x > blue.x;
		break;
	case 1:
		return red.y > blue.y;
		break;
	case 2:
		return red.x < blue.x;
		break;
	case 3:
		return red.y < blue.y;
		break;
	}
}
point move(bool color, int dir) {
	point cur; int nx, ny;
	if (color)cur = red; else cur = blue;

	while (1) {
		nx = cur.x + dx[dir], ny = cur.y + dy[dir];
		if (nx < 0 || nx >= m || ny<0 || ny>n)break;
		if (s[ny][nx] == '#')break;
		else if ((color && nx == blue.x && ny == blue.y)
			|| (!color && nx == red.x && ny == red.y))break;
		if (s[ny][nx] == 'O')return{ 0,0 };
		cur = { nx,ny };
	}
	return cur;
}
void func(int dep) {
	if (dep > 10 || dep >= ans)return;
	point pr = red, pb = blue;
	for (int i = 0; i < 4; i++) {
		bool w = cmp(i);

		if (w) {
			red = move(1, i);
			blue = move(0, i);
		}
		else {
			blue = move(0, i);
			red = move(1, i);
		}

		if (s[blue.y][blue.x] != '#' && s[red.y][red.x] == '#') {
			if (dep < ans)ans = dep;
		}
		else if (s[blue.y][blue.x] == '#');
		else if (red.x == pr.x && red.y == pr.y && blue.x == pb.x && blue.y == pb.y);
		else {
			func(dep + 1);
		}

		red = pr; blue = pb;
	}
}//구슬이 구멍에 들어갔을 때 빼내는 처리 안 함, if문에서 파란구슬 빠졌을 때 빼먹음4
int main() {
	freopen("input.txt", "r", stdin);
	scanf("%d%d ", &n, &m);
	for (int i = 0; i < n; i++)
		scanf("%s", &s[i]);
	for (int i = 0; i < n; i++)for (int j = 0; j < m; j++) {
		switch (s[i][j]) {
		case 'R':
			red = { j,i }; break;
		case 'B':
			blue = { j,i }; break;
		default: break;
		}
	}
	func(1);
	printf("%d", ans == 11 ? -1 : ans);
	return 0;
}

주석처리 해놓은 것 처럼 구슬이 구멍에 빠졌을 때 좌표를 이동해줘야 뒤의 구슬이 이동할 수 있을텐데.... 그걸 처음에 빼먹고 파란구슬만 빠졌을 때 처리해주는 것도 까먹었당 ㅎㅎ