백준 15653 c++ "구슬 탈출 4" -PlusUltraCode-

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

[필자 사고]

BFS구현 문제와 유사하다. 이 문제만의 특이한 점은 구슬의 위치다.

처음에는 백트래킹 으로 문제를 접근했더니 시간 초과가 발생했다.

단순 BFS로 사고로 전화하여 풀었는데 재미난 점이

한번이 많이 이동할 수 있다는 점이다.

필자는 while문을 이용하여 이동거리를 이동시키고 만약 두 구술이 같은 위치에 있다면 

더 많이 이동한 구슬을 한칸 뒤로 이동시키는 전략을 택했다.

 

아이디어 꽤 괜찮은 구현 문제였다.

[코드 해설]

Input

보드 크기 N×M을 입력받고, 문자열로 보드를 채웁니다. 입력 중 ‘R’과 ‘B’를 만나면 각각의 시작 좌표를 저장합니다(현재 코드는 보드에 그대로 R/B 문자를 남겨둡니다).

isInside

주어진 좌표가 보드 범위 안인지 판정합니다. (현재 구현에서는 호출되지 않습니다.)

goToBall

주어진 공의 좌표를 참조로 받아, 특정 방향으로 벽(‘#’)을 만나기 직전까지 또는 구멍(‘O’)에 들어갈 때까지 “직선으로” 굴립니다.

• 벽 앞에서 멈추면 마지막 좌표로 갱신하고 이동 칸 수를 반환합니다.
• 구멍에 들어가면 구멍 좌표로 갱신하고 이동 칸 수+1을 반환합니다.
  이 반환값은 이후 두 공이 같은 칸에 정지했을 때 “누가 더 멀리 이동했는지” 비교하는 데 쓰입니다.

BFS

초기 상태(빨강 시작, 파랑 시작, 횟수 0)를 큐에 넣고 방문 처리합니다. 큐에서 하나 꺼낼 때마다 4방향에 대해:

1. 현재 두 공 좌표를 복사해 각각 goToBall로 같은 방향으로 굴립니다.
2. 파란 공이 ‘O’라면 이 분기는 폐기하고 다음 방향으로 넘어갑니다.
3. 빨간 공이 ‘O’라면 현재 횟수+1을 정답으로 출력하고 isSuccess를 설정한 뒤 종료합니다.
4. 두 공의 최종 좌표가 같다면, 두 공의 이동거리(redDist, blueDist)를 비교해 더 멀리 이동한 공을 해당 방향으로 한 칸 되돌려 겹침을 해소합니다.
5. 새 상태(Ry, Rx, By, Bx)가 방문되지 않았다면 방문 표시 후, 횟수+1과 함께 큐에 넣습니다.

Game_Start

BFS를 실행합니다. 탐색이 끝났는데도 성공하지 못했으면 -1을 출력합니다.

main

Input으로 보드를 읽고, Game_Start를 호출해 문제를 풉니다.

동작 흐름 요약

• 한 번 기울일 때 두 공을 같은 방향으로 끝까지 굴리는 “한 턴”을 goToBall로 구현.
• BFS로 최소 턴을 찾되, 파랑이 빠진 분기는 버리고 빨강만 빠진 순간 정답 확정.
• 두 공이 같은 칸에 멈추면 더 멀리 굴러온 공을 한 칸 뒤로 빼서 충돌 해소.
• 4차원 visited로 중복 상태 방지.

[소스 코드]

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

typedef pair<int, int> Node;
struct queueNode {
	int redY;
	int redX;
	int blueY;
	int blueX;
	int count;
};

int dy[4] = { 0,-1,0,1 };
int dx[4] = { 1,0,-1,0 };


int N, M;
vector<vector<char>> arr;

Node redBall, blueBall;


void Input() {
	cin >> N >> M;
	arr.assign(N, vector<char>(M));

	for (int i = 0; i < N; i++) {
		
		string str;
		cin >> str;
		for (int k = 0; k < M; k++) {
			arr[i][k] = str[k];
			if (arr[i][k] == 'B') {
				blueBall = { i,k };
			}
			else if (arr[i][k] == 'R') {
				redBall = { i,k };
			}
		}
	}
}

bool visited[11][11][11][11];

bool isInside(int sero, int  garo) {
	if (sero >= 0 && sero < N && garo >= 0 && garo < M)return true;
	return false;
}

int goToBall(Node &ballPoint, int dir) {
	int nowSero = ballPoint.first;
	int nowGaro = ballPoint.second;
	int count = 0;
	while (1) {
		int nextSero = nowSero + dy[dir];
		int nextGaro = nowGaro + dx[dir];

		if (arr[nextSero][nextGaro] == '#') {
			ballPoint.first = nowSero;
			ballPoint.second = nowGaro;
			return count;
		}
		if (arr[nextSero][nextGaro] == 'O') {
			ballPoint.first = nextSero;
			ballPoint.second = nextGaro;
			return count + 1;
		}

		nowSero = nextSero;
		nowGaro = nextGaro;
		count++;
	}
}

bool isSuccess = false;

void BFS() {
	queue<queueNode> myQueue;
	myQueue.push({ redBall.first,redBall.second, blueBall.first,blueBall.second, 0 });
	visited[redBall.first][redBall.second][blueBall.first][blueBall.second] = true;

	while (!myQueue.empty()) {
		int nowRedY = myQueue.front().redY;
		int nowRedX = myQueue.front().redX;
		int nowBlueY = myQueue.front().blueY;
		int nowBlueX = myQueue.front().blueX;
		int nowCount = myQueue.front().count;
		myQueue.pop();

		for (int i = 0; i < 4; i++) {
			Node nextRedPoint = { nowRedY,nowRedX };
			Node nextBluePoint = { nowBlueY,nowBlueX };
			int redDist = goToBall(nextRedPoint, i);
			int blueDist = goToBall(nextBluePoint, i);

			if (arr[nextBluePoint.first][nextBluePoint.second] == 'O')continue;
			if (arr[nextRedPoint.first][nextRedPoint.second] == 'O') {
				cout<< nowCount + 1;
				isSuccess = true;
				return;
			}
			if (nextRedPoint.first==nextBluePoint.first &&
				nextRedPoint.second == nextBluePoint.second) {
				if (redDist > blueDist) {
					nextRedPoint.first -= dy[i];
					nextRedPoint.second -= dx[i];
				}
				else {
					nextBluePoint.first -= dy[i];
					nextBluePoint.second -= dx[i];
				}
			}

			if (visited[nextRedPoint.first][nextRedPoint.second][nextBluePoint.first][nextBluePoint.second] == true)continue;
			visited[nextRedPoint.first][nextRedPoint.second][nextBluePoint.first][nextBluePoint.second] = true;
			myQueue.push({ nextRedPoint.first,nextRedPoint.second, nextBluePoint.first,nextBluePoint.second , nowCount + 1 });

		}
	}
}

void Game_Start() {
	BFS();
	if (isSuccess == false) {
		cout << -1;
	}
}

int main(void) {
	Input();
	Game_Start();
}