<C/C++> BOJ 13460: 구슬탈출

오늘부터 하루에 한두문제씩 개별적으로 알고리즘 문제를 풀어보려고 합니다!

 

#include <stdio.h>
#include <queue>
using namespace std;

#define MAXN 10
int N, M;
int RR, RC, BR, BC;
int rcnt, bcnt;
char map[MAXN + 5][MAXN + 5];
int visited[MAXN + 5][MAXN + 5][MAXN + 5][MAXN + 5];
struct DATA { int rr, rc, br, bc, t; };
queue<DATA> q;
static int dr[] = { -1, 1, 0, 0 };
static int dc[] = { 0, 0, -1, 1 };

void tilt(int &r, int &c, int &cnt, int i) {
	for (;;) {
		if (map[r][c] == 'O') break;
		if (map[r + dr[i]][c + dc[i]] == '#')break;
		r += dr[i];
		c += dc[i];
		cnt++;
	}
	
	//printf("%d %d %d\n", r, c, cnt);
}

int BFS(void) { // 문제 꼼꼼히 읽기
	q = {};
	q.push({ RR, RC, BR, BC, 0 });
	visited[RR][RC][BR][BC] = 1;

	while (!q.empty()) {
		DATA cur = q.front(); q.pop();
		if (cur.t >= 10) break; //10회 초과

		for (int i = 0; i < 4; i++) {
			int nrr = cur.rr, nrc = cur.rc, nbr = cur.br, nbc = cur.bc;
			rcnt = 0, bcnt = 0;
			tilt(nrr, nrc, rcnt, i);
			tilt(nbr, nbc, bcnt, i);
			//printf("%d %d %d: %d %d %d %d // %d %d %d %d \n", cur.t, rcnt, bcnt, cur.rr, cur.rc, cur.br, cur.bc, nrr, nrc, nbr, nbc);

			if (map[nbr][nbc] == 'O') continue; // 파란구슬 구멍에 들어감
			if (map[nrr][nrc] == 'O') return cur.t + 1; // 빨간구슬 구멍에 들어감
			if (nrr == nbr && nrc == nbc) { // 겹치면 더많이 움직인 구슬 한칸 이전으로 보내주기
				if (rcnt > bcnt) nrr -= dr[i], nrc -= dc[i];
				else nbr -= dr[i], nbc -= dc[i];
			}
			if (visited[nrr][nrc][nbr][nbc]) continue; // 방문한 적 있으면 

			visited[nrr][nrc][nbr][nbc] = 1;
			q.push({ nrr, nrc, nbr, nbc, cur.t + 1 });
		}
	}
	return -1;
}

void Solve(void) {
	for (int i = 2; i < N; i++) {
		for (int j = 2; j < M; j++) {
			if (map[i][j] == 'R') {
				RR = i, RC = j;
			}
			else if (map[i][j] == 'B') {
				BR = i, BC = j;
			}
		}
	}

	int ans = BFS();
	printf("%d\n", ans);
}

void InputData(void) {
	scanf("%d %d", &N, &M);
	for (int i = 1; i <= N; i++) {
		scanf("%s", &map[i][1]); // '&' 꼭 붙이기
	}
}
int main(void) {
	InputData();
	Solve();
	return 0;
}

 

<What I learned>

문제 꼼꼼히 읽쟈...
이전에 풀었던 문제(구슬 집어넣기)와 거의 동일해서 문제를 대충 읽었다.

한칸씩 움직인다 생각하고 풀었다.
하지만 한번 움직이면 못움직일 때까지(벽에 부딪히거나 구슬에 들어간 경우) 계속 움직이는 것이기에 
방향 결정해주는 for문 안에 while문을 사용해서 끝까지 움직여줘야 한다.

구슬이 겹치는 경우가 생겼을 때 한 구슬을 이전의 자리로 옮겨줘야 하는데
빨간 구슬과 파란 구슬 각각 cnt를 비교해서 더 큰 걸 이전 자리로 옮겨준다.

이전 풀었던 문제와 달리 유효성 검사 순서도 중요
겹쳤을 경우 그에 맞게 바꿔준 후 유효성 검사하기