[C++]백준2589번 보물섬

오늘은 백준2589번 보물섬 문제를 풀어보도록 하자.

BFS문제로 큐의 턴 관리가 중요했던 문제다. 최단 거리로 이동하는 시간을 구해야하므로 BFS로 구현을 하였다.

문제는 다음과 같다.

                               [접근법]

  1. 만일 map이 L이면 bfs 돌린다.

  2. 이 때 중요한건 큐 사이즈 만큼 돌려줘야한다는 것이다. 왜냐하면 큐 사이즈만큼 돌려주지 않으면 최단거리가 아님에도 불구하고 cnt값을 증가시키기 때문에
  원하는 이동 시간을 얻을 수 없다.

                                     [코드]
#include <iostream>
#include <queue>
using namespace std;
char map[50][50];
bool visit[50][50];
int dir[4][2] = { {-1,0}, {0,1},{1,0},{0,-1} };
int R, C, answer = 0;
struct pos {
	int y;
	int x;
};
queue<pos>Q;

void Init_visit() {
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			visit[i][j] = false;
		}
	}
}

bool Inbound(int y, int x) {
	if (y >= 0 && y < R && x >= 0 && x < C) {
		return true;
	}
	return false;
}

void bfs() {
	int cnt = 0;
	while (!Q.empty()) {
		int size_of_Q = Q.size();

		for (int j = 0; j < size_of_Q; j++) {
			int y = Q.front().y;
			int x = Q.front().x;

			Q.pop();

			for (int i = 0; i < 4; i++) {
				int my = y + dir[i][0];
				int mx = x + dir[i][1];

				if (Inbound(my, mx)) {
					if (!visit[my][mx] && map[my][mx] == 'L') {
						Q.push({ my,mx });
						visit[my][mx] = true;
					}
				}
			}
		}
		cnt++;
	}
	if (answer < cnt) {
		answer = cnt;
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> R >> C;

	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			cin >> map[i][j];
		}
	}

	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			if (map[i][j] == 'L') {
				Q.push({ i,j });
				visit[i][j] = true;
				bfs();
				Init_visit();
			}
		}
	}
	cout << answer - 1 << '\n';
}