[BOJ] 17198 : Bucket Brigade - travelbeeee

문제 : https://www.acmicpc.net/problem/17198

---

[ 알고리즘풀이 ]

'B' 에서 'L' 까지 'R'을 피해서 탐색하는 문제로 BFS 탐색을 이용하면 쉽게 문제를 해결할 수 있다.

#include<iostream>
#include<queue>

using namespace std;

int dx[4] = { -1,0,1,0 }, dy[4] = { 0, -1, 0, 1 };
bool visited[10][10] = {};
char map[10][11] = {};
queue<pair<pair<int, int>, int>> BFS;

bool check(int x, int y) {
	if (0 <= x && x < 10 && 0 <= y && y < 10 && map[x][y] != 'R' && visited[x][y] == false)
		return true;
	return false;
}
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	for (int i = 0; i < 10; i++)
		cin >> map[i];
	int barnX, barnY, lakeX, lakeY;
	for (int i = 0; i < 10; i++)
		for (int j = 0; j < 10; j++) {
			if (map[i][j] == 'L') {
				lakeX = i, lakeY = j;
			}
			if (map[i][j] == 'B') {
				barnX = i, barnY = j;
			}
		}
	visited[barnX][barnY] = true;
	BFS.push(make_pair(make_pair(barnX, barnY),0));
	while (!BFS.empty()) {
		pair<pair<int, int>, int> temp = BFS.front();
		BFS.pop();
		int curX = temp.first.first, curY = temp.first.second, length = temp.second;
		if (map[curX][curY] == 'L') {
			cout << length - 1 << '\n';
			break;
		}
		for (int i = 0; i < 4; i++) {
			int nextX = curX + dx[i], nextY = curY + dy[i];
			if (check(nextX, nextY)) {
				visited[nextX][nextY] = true;
				BFS.push(make_pair(make_pair(nextX, nextY), length + 1));
			}
		}
	}
	return 0;
}

---