백준 13460번 - 구슬 탈출2

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

 

 

골드1은 참 어렵다..

 

그래도 내가 많이 해본 bfs문제이기도 하고 구현의 난이도와 시뮬레이션으로 골드1 난이도를 받은 문제라 다행히 풀어낼 순 있었다. 단연 중요한 건 어떻게 방문체크를 할 것이냐인데, 

 

난 빨간 구슬, 파란 구슬을 나누어

 

[x좌표][y좌표][방향][빨간색 or 파란색] 4차원 배열을 만들어서

 

[x좌표][y좌표][방향][빨간색] || [x좌표][y좌표][방향][파란색]

 

으로 방문 처리를 하니 30퍼센트에서 틀렸습니다가 발생했다... 

 

그리고 정답 처리가 된 것은 visited[nextrx][nextry][nextbx][nextby] 이런식으로 해야한다. 흠... 아무리 생각해도 위 방법도 될 것 같은데 왜 안되는지 모르겠다.

 

#include <iostream>
#include <queue>

using namespace std;
bool red_flag = false;
bool blue_flag = false;

	int dx[] = {0,0,1,-1};
	int dy[] = {1,-1,0,0};
	int N, M;
	bool visited[11][11][11][11] = {false,};

	int des_x, des_y;

	class Node {
	public:
		int rx, ry;
		int bx, by;
		int pointer;
		int cnt;
		vector<vector<char>> miros;

		Node(){}

		Node(int rx, int ry, int bx, int by, int pointer, int cnt, vector<vector<char>> miros){
			this->bx = bx;
			this->by = by;
			this->rx = rx;
			this->ry = ry;
			this->pointer = pointer;
			this->cnt = cnt;
			this->miros = miros;
		}
	};

	queue<Node> q;

	int answer = 10000;

	bool range(int x, int y){
		return x < N && y < M && x > -1 && y > -1;
	}

	pair<int, int> move(int col, int pos, int x, int y, vector<vector<char>>& miros){
		int nextx = x + dx[pos];
		int nexty = y + dy[pos];

		while(miros[nextx][nexty] == '.'){
			nextx += dx[pos];
			nexty += dy[pos];
		}

		if(miros[nextx][nexty] == 'O'){
			if(col == 0) {
				red_flag = true;
			}
			else {
				blue_flag = true;
			}
			miros[x][y] = '.';
			// cout << "블루 플레그 : " << blue_flag << endl;
			// cout << "레드 플레그 : " << red_flag << endl;
		}
		else{
			//cout << "과연 뭘가" << miros[nextx][nexty] << endl;
			if(col == 0){
				miros[x][y] = '.';
				miros[nextx - dx[pos]][nexty - dy[pos]] = 'R';
				
			}else{				
				miros[x][y] = '.';
				miros[nextx - dx[pos]][nexty - dy[pos]] = 'B';
			}
		}

		return {nextx - dx[pos], nexty - dy[pos]};
	}

	void bfs(){
		//cout << "도착지 : " <<  des_x << " " << des_y << '\n';

		while(!q.empty()){

			Node nowNode = q.front();
			q.pop();
			//cout << nowNode.rx << " " << nowNode.ry << endl;
	

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

					red_flag = false;
					blue_flag = false;

				int nextrx = nowNode.rx;
				int nextry = nowNode.ry;
				int nextbx = nowNode.bx;
				int nextby = nowNode.by;
				vector<vector<char>> nextMiro = nowNode.miros;

				if(i == 0){ // 오른쪽
					if(nextry < nextby){ // 블루 먼저
						pair<int, int> nextBlue = move(1, i, nextbx, nextby, nextMiro);
						nextbx = nextBlue.first;
						nextby = nextBlue.second;

						pair<int, int> nextRed = move(0, i, nextrx, nextry,nextMiro);
						nextrx = nextRed.first;
						nextry = nextRed.second;
					}else{
						pair<int, int> nextRed = move(0, i, nextrx, nextry,nextMiro);
						nextrx = nextRed.first;
						nextry = nextRed.second;

						pair<int, int> nextBlue = move(1, i, nextbx, nextby,nextMiro);
						nextbx = nextBlue.first;
						nextby = nextBlue.second;
					}
				}else if (i == 1){
					if(nextry > nextby){ // 블루 먼저
						pair<int, int> nextBlue = move(1, i, nextbx, nextby,nextMiro);
						nextbx = nextBlue.first;
						nextby = nextBlue.second;

						pair<int, int> nextRed = move(0, i, nextrx, nextry,nextMiro);
						nextrx = nextRed.first;
						nextry = nextRed.second;
					}else{
						pair<int, int> nextRed = move(0, i, nextrx, nextry, nextMiro);
						nextrx = nextRed.first;
						nextry = nextRed.second;

						pair<int, int> nextBlue = move(1, i, nextbx, nextby, nextMiro);
						nextbx = nextBlue.first;
						nextby = nextBlue.second;
					}
				}else if (i == 2){ // 아래
					if(nextrx < nextbx){ // 블루 먼저
						pair<int, int> nextBlue = move(1, i, nextbx, nextby, nextMiro);
						nextbx = nextBlue.first;
						nextby = nextBlue.second;

						pair<int, int> nextRed = move(0, i, nextrx, nextry , nextMiro);
						nextrx = nextRed.first;
						nextry = nextRed.second;
					}else{
						pair<int, int> nextRed = move(0, i, nextrx, nextry, nextMiro);
						nextrx = nextRed.first;
						nextry = nextRed.second;

						pair<int, int> nextBlue = move(1, i, nextbx, nextby, nextMiro);
						nextbx = nextBlue.first;
						nextby = nextBlue.second;
					}
				}else if( i == 3){
					if(nextrx > nextbx){ // 블루 먼저
						pair<int, int> nextBlue = move(1, i, nextbx, nextby, nextMiro);
						nextbx = nextBlue.first;
						nextby = nextBlue.second;

						pair<int, int> nextRed = move(0, i, nextrx, nextry, nextMiro);
						nextrx = nextRed.first;
						nextry = nextRed.second;
					}else{
						pair<int, int> nextRed = move(0, i, nextrx, nextry, nextMiro);
						nextrx = nextRed.first;
						nextry = nextRed.second;

						pair<int, int> nextBlue = move(1, i, nextbx, nextby, nextMiro);
						nextbx = nextBlue.first;
						nextby = nextBlue.second;
					}
				}
				

				if(blue_flag) continue;
				if(red_flag){
					answer = min(answer, nowNode.cnt + 1);
					//cout << answer << endl;
					continue;
				}

				// 하나라도 방문한 적이 없음
				if(visited[nextrx][nextry][nextbx][nextby] == false){
					visited[nextrx][nextry][nextbx][nextby] = true;

					red_flag = false;
					blue_flag = false;

				

					Node nextNode(nextrx, nextry, nextbx, nextby, i, nowNode.cnt + 1, nextMiro);
					q.push(nextNode);
				}
			}
		}
	}

	int main(){
		cin >> N >> M;
		vector<vector<char>> miro(11, vector<char>(11));

		Node firstNode;

		for(int i = 0; i < N; i++){
			string tmp; cin >> tmp;
			for(int j = 0; j < M; j++){
				miro[i][j] = tmp[j];

				if(miro[i][j] == 'R'){
					firstNode.rx = i;
					firstNode.ry = j;
				}else if(miro[i][j] == 'B'){
					firstNode.bx = i;
					firstNode.by = j;
				}else if(miro[i][j] == 'O'){
					des_x = i;
					des_y = j;
				}
			}
		}

		firstNode.cnt = 0;
		firstNode.pointer = -1;
		firstNode.miros = miro;

		q.push(firstNode);

		bfs();
		if(answer > 10) cout << -1 << endl;
		else if(answer == 1000) cout << -1 << endl;
 		else cout << answer << '\n';
	}