[백준][13460][c++] 구슬 탈출2

구슬 탈출2 문제 링크

[내 풀이]

알고리즘

고려해야 할 것이 많은 만큼 세세하기 신경써서 짜야 한다. 안 그러면 실패의 늪에 계속 빠지게 된다. 시뮬레이션이랑 최단 거리가 합쳐진 것이기 때문에 BFS를 쓰기로 결정했다. 빨간 구슬 먼저 움직인다음 그 방향에 맞춰 파란 구슬을 움직이기로 했다. 하지만 두 구슬이 겹쳐지는 경우도 있으니 더 긴 거리를 움직인 구슬이 한 칸 뒤로 움직이는 것을 해줘야 한다. 그리고 BFS에서 꼭 해줘야 하는 중복 검사는 4차원 배열을 만들어서 빨간 구슬, 파란 구슬이 멈추었을 때의 상태를 검사하는 것으로 했다.

BFS에서 중복검사하는 방법을 잘 세우는 것이 중요한 것 같다. 상태는 다른 상태가 되었다 돌아온다한들 목적지까지의 거리가 동일해야 한다. 즉 빠짐없이 다 표현해야 한다.

자료구조

• 중복 검사를 위한 4차원 bool 배열
• 구슬의 정보를 저장하기 위한 marble struct {y좌표, x좌표, 거리, O을 만났는지 확인하기 위한 bool}
• 보드 정보 2차원 배열

#include <iostream>
#include <string>
#include <queue>
#define N_MAX 11

using namespace std;

int N, M;
char map[N_MAX][N_MAX];
bool visited[N_MAX][N_MAX][N_MAX][N_MAX] = {false,};

int dir_y[4] = { 0,0,1,-1 };
int dir_x[4] = { 1,-1,0,0 };

int inverse_dir(int dir) {
	if (dir == 0) return 1;
	else if (dir == 1) return 0;
	else if (dir == 2) return 3;
	else if (dir == 3) return 2;
	return -1;
}

struct marble {
	int y;
	int x;
	int cost = 0;
	bool flag = false;
};


int bfs(marble Red, marble Blue) {
	queue<pair<marble, marble>> q;

	q.push(make_pair(Red, Blue));
	visited[Red.y][Red.x][Blue.y][Blue.x] = true;

	while (!q.empty()) {
		pair<marble, marble> cur_marble = q.front();
		q.pop();

		marble cur_red = cur_marble.first;
		marble cur_blue = cur_marble.second;

		if (cur_red.cost >= 10) break;
		
		
		for (int dir = 0; dir < 4; dir++) {
			marble new_red, new_blue;

			int prev_y = cur_red.y;
			int prev_x = cur_red.x;

			int red_move = 0;

			int new_y, new_x;
			//빨간 구슬 move!
			while (1) {
				new_y = prev_y + dir_y[dir];
				new_x = prev_x + dir_x[dir];

				if (map[new_y][new_x] == '#') {
					//flag = true;
					new_red.y = prev_y; new_red.x = prev_x; new_red.cost = cur_red.cost + 1;
					break;
					
				}
				else if (map[new_y][new_x] == 'O') {
					//flag = true;
					new_red.y = new_y; new_red.x = new_x; new_red.cost = cur_red.cost + 1;
					new_red.flag = true;
					break;
				}
				
				prev_y = new_y;
				prev_x = new_x;
				red_move++;
			}


			int prev_blue_y = cur_blue.y;
			int prev_blue_x = cur_blue.x;
			int blue_move = 0;

			int new_blue_y, new_blue_x;
			//파란 구슬 move
			while (1) {
				new_blue_y = prev_blue_y + dir_y[dir];
				new_blue_x = prev_blue_x + dir_x[dir];

				if (map[new_blue_y][new_blue_x] == '#') {
					new_blue.y = prev_blue_y;
					new_blue.x = prev_blue_x;
					break;
				}
				else if (map[new_blue_y][new_blue_x] == 'O') {
					new_blue.y = new_blue_y;
					new_blue.x = new_blue_x;
					new_blue.flag = true;
					break;
				}

				prev_blue_y = new_blue_y;
				prev_blue_x = new_blue_x;
				blue_move++;
			}

			//파란 구슬은 O을 만나면 실패이기 때문에 탐색에다 넣어주지 않음
			if (new_blue.flag ) continue;
			//파란구슬은 O을 만나지 않앗고 빨간 구슬이 만낫을 시 조건 만족해 거리찍고 끝
			if (new_red.flag && !new_blue.flag) return new_red.cost;
			//if (new_red.cost >= 11) break;

			//파란 구슬이라 빨간 구슬이 O가 아닌 곳에서 겹친거니 온 거리가 긴 구슬이 step back
			if (new_red.y == new_blue.y && new_red.x == new_blue.x) {
				if (red_move < blue_move) {
					new_blue.y = new_blue.y - dir_y[dir];
					new_blue.x = new_blue.x - dir_x[dir];
				}
				else {
					new_red.y = new_red.y - dir_y[dir];
					new_red.x = new_red.x - dir_x[dir];
				}
			}

			if (visited[new_red.y][new_red.x][new_blue.y][new_blue.x]) continue;
			q.push(make_pair(new_red, new_blue));
			visited[new_red.y][new_red.x][new_blue.y][new_blue.x] = true;
		}
		
		
	}
	return -1;
}

int main() {
	cin >> N >> M;
	marble Red;
	marble Blue;
	for (int y = 0; y < N; y++) {
		string str;
		cin >> str;
		for (int x = 0; x < M; x++) {
			map[y][x] = str[x];
			if (map[y][x] == 'R') {
				Red.y = y;
				Red.x = x;
				//map[y][x] = '.';
			}
			else if (map[y][x] == 'B') {
				Blue.y = y;
				Blue.x = x;
				//map[y][x] = '.';
			}
		}
	}
	
	int answer = bfs(Red, Blue);
	cout << answer << "\n";
	return 0;
}

[총평]
알고리즘도 덜 세웠고 세세한 것들도 틀려서 하루 걸린 것 같다. 코드를 잘 알아볼 수 있게 짜는 것은 협업하는 다른 사람들을 위한 것 뿐만이 아닌 코딩을 빨리 하기 위해서 임을 느꼇다.

[참고 자료]
https://yabmoons.tistory.com/229
https://codingwell.tistory.com/55