백준 13460 / CPP / bfs

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

이 문제는 겁나 복잡해보였지만 막상 풀고나니 이해하기 쉬웠다

그냥 두가지 케이스 빨간공 파란공 각각 움직인다음 겹칠때 혹은 구멍에 들어갈때의 조건식만 추가해주면 되었다

#include<iostream>
#include<string>
#include<queue>
using namespace std;
int arr[10][10];
struct INFO {
	int Rx, Ry, Bx, By, count;
};
int n, m;
INFO start;
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,-1,1 };
int visited[11][11][11][11] = { 0, };
int bfs() {
	queue<INFO> bfsQ;
	bfsQ.push(start);

	int ans = -1;
	visited[start.Rx][start.Ry][start.Bx][start.By] = 1;
	while (!bfsQ.empty()) {
		INFO cur = bfsQ.front();
		bfsQ.pop();
		if (cur.count > 10)break;

		if (arr[cur.Rx][cur.Ry] == 4 && arr[cur.Bx][cur.By] != 4) {
			ans = cur.count;
			break;
		}

		for(int i=0; i<4; i++){
			int nextRy = cur.Ry;
			int nextRx = cur.Rx;
			int nextBy = cur.By;
			int nextBx = cur.Bx;
			while (1) {
				if (arr[nextRx][nextRy] != 1 and arr[nextRx][nextRy] != 4) {
					nextRx += dx[i];
					nextRy += dy[i];
				}
				else {
					if (arr[nextRx][nextRy] == 1) {
						nextRx -= dx[i]; 
						nextRy -= dy[i]; //벽일 경우 이전위치로
					}
					break;
				}
			}

			//blue 구슬 벽이나 구멍일때까지 한 방향으로 이동함
			while (1) {
				if (arr[nextBx][nextBy] != 1 and arr[nextBx][nextBy] != 4) {
					nextBx += dx[i];
					nextBy += dy[i];
				}
				else {
					if (arr[nextBx][nextBy] == 1) {
						nextBx -= dx[i]; 
						nextBy -= dy[i]; //벽일 경우 이전위치로
					}
					break;
				}
			}

			//red와 blue가 겹칠 경우
			if (nextRx == nextBx and nextRy == nextBy) {
				if (arr[nextRx][nextRy] != 4) {
					int red_dist = abs(nextRx - cur.Rx) + abs(nextRy - cur.Ry);
					int blue_dist = abs(nextBx - cur.Bx) + abs(nextBy - cur.By);

					if (blue_dist > red_dist) {
						nextBx -= dx[i];
						nextBy -= dy[i];
					}
					else {
						nextRx -= dx[i];
						nextRy -= dy[i];
					}
				}
			}

			//방문여부 확인
			if (visited[nextRx][nextRy][nextBx][nextBy] == 0) {
				visited[nextRx][nextRy][nextBx][nextBy] = 1;
				INFO next;
				next.Rx = nextRx;
				next.Ry = nextRy;
				next.Bx = nextBx;
				next.By = nextBy;
				next.count = cur.count + 1;

				bfsQ.push(next);

			}
		}

	}
	return ans;
}

int main() {
	cin >> n >> m;
	string input;

	for (int i = 0; i < n; i++) {
		cin >> input;
		for (int j = 0; j < m; j++) {
			if (input[j] == '#') {
				arr[i][j] = 1;
			}
			else if (input[j] == 'R') {
				arr[i][j] = 2;
				start.Rx = i;
				start.Ry = j;
			}
			else if (input[j] == 'B') {
				arr[i][j] = 3;
				start.Bx = i;
				start.By = j;
			}
			else if (input[j] == 'O') {
				arr[i][j] = 4;
			}
		}
	}
	start.count = 0;
	cout << bfs();
}