글 읽기 - 구슬탈출 15653 예외가 뭔지모르겠네요. 도와주세요.

jds 1년 전 0

안녕하세요. 기본 테스트 케이스는 맞는데 정답을 못찾겠습니다. 도와주세요.

제가 접근한 방식은 이렇습니다.

4방향에 따라 먼저 움직이는 구슬을 찾습니다(붙어있는 경우를 대비하여).
먼저 움직이는 구슬을 방향에 따라 움직입니다. 만약 구멍에 빠지면 멈춥니다. 다른구슬 혹은 벽에 다다르면 이전 위치로 돌아갑니다.
나머지 구슬을 방향에 따라 움직입니다. 만약 구멍에 빠지면 멈춥니다. 이때, 다른구슬 혹은 벽에 다다르면 이전 위치로 돌아갑니다.

이과정을 반복하면서 BFS를 구현해보았습니다.

아무리봐도 어떤 케이스에서 안되는건지 모르겠네요.

한수 알려주시면 진심으로 감사드리겠습니다.

#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <cstring>

using namespace std;

int dist[10][10][10][10];

int dx[] = { -1, 1, 0, 0 };
int dy[] = { 0, 0, -1, 1 };
// 위, 아래, 왼쪽, 오른쪽

class Node{

public:
	int rx;
	int ry;
	int bx;
	int by;
};

//int hx, hy;

pair<bool, bool> get_result(vector<string>& b, int& rx, int& ry, int& bx, int& by, int direction){


	bool hrcheck = false;
	bool hbcheck = false;

	bool bFirst = false;

	int n = b.size();
	int m = b[0].size();

	if (direction == 0){
		//위
		//작은값이 더 위에있는 것
		if (ry == by && abs(rx - bx) == 1){
			if (rx > bx){
				bFirst = true;
			}
		}


	}
	else if (direction == 1){
		//아래
		//큰값이 더 아래에 있는 것
		if (ry == by && abs(rx - bx) == 1){
			if (rx < bx){
				bFirst = true;
			}
		}
	}
	else if (direction == 2){
		//왼쪽
		//작은 값이 왼쪽
		if (rx == bx && abs(ry - by) == 1){
			if (ry > by){
				bFirst = true;
			}
		}

	}
	else if (direction == 3){
		//오른쪽
		if (rx == bx && abs(ry - by) == 1){
			if (ry < by){
				bFirst = true;
			}
		}
	}

	//b[nrx][nry] = 'R';
	//b[nbx][nby] = 'B';

	while (true){
		if (bFirst){

			bx += dx[direction];
			by += dy[direction];
			
			if (bx < 0 || bx >= n || by < 0 || by >= m){
				bx -= dx[direction];
				by -= dy[direction];
				break;
			}
			
			if (b[bx][by] == 'O'){
				hbcheck = true;
				break;
			}

			if (b[bx][by] == '#' || (rx == bx && ry == by)){
				bx -= dx[direction];
				by -= dy[direction];
				//b[bx][by] = 'B';
				break;
			}

		}
		else{

			rx += dx[direction];
			ry += dy[direction];
			
			if (rx < 0 || rx >= n || ry < 0 || ry >= m){
				rx -= dx[direction];
				ry -= dy[direction];
				break;
			}
			
			if (b[rx][ry] == 'O'){
				hrcheck = true;
				break;
			}

			if (b[rx][ry] == '#' || (rx == bx && ry == by)){
				rx -= dx[direction];
				ry -= dy[direction];
				//b[rx][ry] = 'R';
				break;
			}
		}
	}

	while (true){
		if (!bFirst){

			bx += dx[direction];
			by += dy[direction];
			
			if (bx < 0 || bx >= n || by < 0 || by >= m){
				bx -= dx[direction];
				by -= dy[direction];
				break;
			}
			
			if (b[bx][by] == 'O'){
				hbcheck = true;
				break;
			}

			if (b[bx][by] == '#' || (rx == bx && ry == by)){
				bx -= dx[direction];
				by -= dy[direction];
				//b[bx][by] = '.';
				break;
			}

		}
		else{
			
			rx += dx[direction];
			ry += dy[direction];
			
			if (rx < 0 || rx >= n || ry < 0 || ry >= m){
				rx -= dx[direction];
				ry -= dy[direction];
				break;
			}
			
			if (b[rx][ry] == 'O'){
				hrcheck = true;
				break;
			}

			if (b[rx][ry] == '#' || (rx == bx && ry == by)){
				//b[rx][ry] = '.';
				rx -= dx[direction];
				ry -= dy[direction];
				break;
			}
		}
	}

	//

	pair<bool, bool> result;
	//cout << "Direction :" << direction << "\n";

	if (hrcheck == true && hbcheck == true){
		result = make_pair(true, true);
	}
	else if (hrcheck == true && hbcheck == false){
		result = make_pair(true, false);
	}
	else if (hrcheck == false && hbcheck == true){
		result = make_pair(false, true);
	}
	else{
		result = make_pair(false, false);
	}

	//b[nrx][nry] = '.';
	//b[nbx][nby] = '.';

	return result;
}

int main() {

	// your code goes here
	int row, col;
	int ans = -1;

	scanf("%d %d", &row, &col);

	vector<string> board;

	for (int i = 0; i<row; i++){
		string s;
		cin >> s;
		board.push_back(s);
	}

	int rx, ry, bx, by;

	for (int i = 0; i<row; i++){
		for (int j = 0; j<col; j++){
			/*
			if (board[i][j] == 'O'){
			hx = i;
			hy = j;
			}
			*/
			if (board[i][j] == 'R'){
				rx = i;
				ry = j;
				board[i][j] = '.';
			}
			else if (board[i][j] == 'B'){
				bx = i;
				by = j;
				board[i][j] = '.';
			}
		}
	}

	queue<Node> q;
	Node n;
	n.rx = rx;
	n.ry = ry;
	n.bx = bx;
	n.by = by;

	memset(dist, -1, sizeof(dist));

	q.push(n);
	dist[rx][ry][bx][by] = 0;

	bool found = false;

	while (!q.empty()){

		Node n = q.front();
		q.pop();

		for (int direction = 0; direction<4; direction++){

			int nrx = n.rx, nry = n.ry, nbx = n.bx, nby = n.by;

			//최종 위치 및 결과
			pair<bool, bool> result = get_result(board, nrx, nry, nbx, nby, direction);

			//cout << "Result : " << result.first << result.second<<"\n";
			if (result.second == true){
				continue;
			}

			if (result.first == true){
				ans = dist[n.rx][n.ry][n.bx][n.by] + 1;
				found = true;
				break;

			}

			if (dist[nrx][nry][nbx][nby] != -1) continue;

			Node newNode;
			newNode.rx = nrx;
			newNode.ry = nry;
			newNode.bx = nbx;
			newNode.by = nby;

			q.push(newNode);
			dist[nrx][nry][nbx][nby] = dist[n.rx][n.ry][n.bx][n.by] + 1;

		}

		if (found){
			break;
		}
	}

	cout << ans << "\n";
	return 0;

}

jds 1년 전 0

각 예외처리에서

이부분을 없애야했습니다. >> abs(rx - bx) == 1

바로 구슬이 옆에있을 경우만 생각했는데 그렇지 않더군요.

반례찾아서 해결했습니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ACM-ICPC

구슬탈출 15653 예외가 뭔지모르겠네요. 도와주세요.

jds 1년 전 0

jds 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말