์•Œ๊ณ ๋ฆฌ์ฆ˜

  • ํ‘ธ๋Š” ๋ฐฉ๋ฒ•์€ bfs์ง€๋งŒ, ๊ตฌํ˜„์ด ๋” ๊นŒ๋‹ค๋กœ์šด ๋ฌธ์ œ์ด๋‹ค.
  • visit์€ ๋นจ๊ฐ„๊ตฌ์Šฌ, ํŒŒ๋ž€๊ตฌ์Šฌ์˜ ์œ„์น˜๋ฅผ ๋™์‹œ์— ๊ธฐ๋กํ•˜์—ฌ ๋‘ ๊ตฌ์Šฌ ๋ชจ๋‘ ๊ฐ™์€ ์ž๋ฆฌ๋กœ ๋‹ค์‹œ ๊ฐ€์ง€ ์•Š๋„๋ก ํ•œ๋‹ค.
  • ๊ฐ ๋ฐฉํ–ฅ์œผ๋กœ ๊ธฐ์šฐ๋ฆด๋•Œ๋Š” ์ผ๋‹จ ํ•œ์ชฝ์„ ๋จผ์ € ๋ณด๋‚ธ๋‹ค๊ณ  ๊ฐ€์ •ํ•˜๊ณ , ์‹ค์ œ๋กœ ๋จผ์ € ๋ณด๋‚ด๋Š”์ง€ ๊ฒ€์‚ฌํ•œ ํ›„ ์•„๋‹ˆ๋ผ๋ฉด ๋‹ค๋ฅธ์ชฝ์„ ๋จผ์ € ๋ณด๋‚ธ๋‹ค.
  • ํ•œ์ชฝ์ด ๊ตฌ๋ฉ์— ๋จผ์ € ๋น ์ง€๋ฉด, (-1,-1) ์œ„์น˜๋กœ ๋ณด๋‚ด์–ด ์ถฉ๋Œ์ด ๋ฐœ์ƒํ•˜์ง€ ์•Š๋„๋ก ํ•œ๋‹ค.

์ฝ”๋“œ

#include <iostream>
#include <list>
#define INF 2000000000;
 
using namespace std;
 
struct node {
	pair<int, int> r;
	pair<int, int> b;
	int d;
};
 
int map[10][10], n, m, os[4][2] = { {-1,0}, {0,1}, {1, 0}, {0,-1} };
pair<int, int> h, r, b;
bool visit[10][10][10][10];
list<node> l;
 
int bfs();
int min(int a, int b) {
	return a < b ? a : b;
}
 
int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		string a;
		cin >> a;
		for (int j = 0; j < m; j++) {
			map[i][j] = a[j];
			switch (map[i][j]) {
			case 'R':
				r = { i,j };
				break;
			case 'B':
				b = { i,j };
				break;
			case 'O':
				h = { i,j };
			}
		}
	}
 
	cout << bfs();
}
 
int bfs() {
	visit[r.first][r.second][b.first][b.second] = true;
	l.push_back({ {r.first, r.second}, {b.first, b.second}, 0 });
 
	int ans = INF;
	while (!l.empty()) {
		node cur = l.front();
		l.pop_front();
 
		for (int i = 0; i < 4; i++) {
			int rr = cur.r.first, rc = cur.r.second, br = cur.b.first, bc = cur.b.second, nd = cur.d + 1;
			bool rf = true;
			if (i % 2 == 0 && rc == bc) {
				if (i == 0 && rr > br)
					rf = false;
				else if (i == 2 && rr < br)
					rf = false;
			}
			else if (i % 2 == 1 && rr == br) {
				if (i == 1 && bc > rc)
					rf = false;
				else if (i == 3 && bc < rc)
					rf = false;
			}
			bool rh = false, bh = false;
			if (rf) {
				while (map[rr + os[i][0]][rc + os[i][1]] != '#') {
					rr += os[i][0];
					rc += os[i][1];
					if (map[rr][rc] == 'O') {
						rh = true;
						rr = rc = -1;
						break;
					}
				}
				while (map[br + os[i][0]][bc + os[i][1]] != '#' && (br + os[i][0] != rr|| bc + os[i][1] != rc)) {
					br += os[i][0];
					bc += os[i][1];
					if (map[br][bc] == 'O') {
						bh = true;
						break;
					}
				}
			}
			else {
				while (map[br + os[i][0]][bc + os[i][1]] != '#') {
					br += os[i][0];
					bc += os[i][1];
					if (map[br][bc] == 'O') {
						bh = true;
						br = bc = -1;
						break;
					}
				}
				while (map[rr + os[i][0]][rc + os[i][1]] != '#' && (rr + os[i][0] != br || rc + os[i][1] != bc)) {
					rr += os[i][0];
					rc += os[i][1];
					if (map[rr][rc] == 'O') {
						rh = true;
						break;
					}
				}
			}
 
			if (rh && !bh)
				ans = min(ans, nd);
			else if (!rh && !bh && !visit[rr][rc][br][bc]) {
				visit[rr][rc][br][bc] = true;
				l.push_back({ {rr, rc}, {br, bc}, nd });
			}
		}
	}
 
	return ans == 2000000000 ? -1 : ans;
}