백준 2589번 보물섬 C++ BFS, 브루트포스 알고리즘

리뷰

진짜 아무리봐도 잘못된게 없는데 계속 틀려서 다시 보니 브루트포스를 돌리는 과정에서 n * m크기가 아닌 n * n크기로 돌리고 있었다... 근데 왜 97% 까지 맞는거야?

 

문제 풀이

n 크기의 문자열을 받아와 준 뒤 n * m크기의 for문을 개행하고 현재 위치가 L일 경우 bfs를 시작한다.

현재 위치와 이동 횟수 0을 큐에 넣어주고 방문 체크용 2차 배열을 0으로 초기화 하고 현 위치를 방문 체크해 준다.

while루프를 돌려 4방향을 체크하고 갈 수 있는 공간이라면 방문 체크 및 이동 횟수를 1 올려 준 후 큐에 추가한다.

이동 횟수가 변경 되었으므로 현재 이동 횟수가 최대 이동 횟수 보다 클 경우 갱신해 준다.

for문이 종료된 후 최대 이동 횟수를 출력해 준다.

 

참고 사항

반복문을 사용할땐 항상 범위를 잘 체크해 주자.

 

 

정답 코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int n, m, max_time = 0;
vector<string> lst;

int dx[] = { 0, 0, 1 ,-1 };
int dy[] = { 1, -1, 0, 0 };

struct Pos {
	int x, y, t;
};

void bfs(Pos pos) {
	queue<Pos> q;
	q.push(pos);
	vector<vector<int>> v(n, vector<int>(m, 0));
	v[pos.x][pos.y] = 1;

	while (!q.empty()) {
		Pos now = q.front();
		q.pop();
		int x = now.x, y = now.y, t = now.t;
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i], ny = y + dy[i];
			if (0 <= nx && nx < n && 0 <= ny && ny < m && !v[nx][ny] && lst[nx][ny] == 'L') {
				v[nx][ny] = v[x][y] + 1;
				q.push({ nx, ny, t + 1 });
				max_time = max(max_time, t + 1);
			}
		}
	}
}

int main() {
	cin >> n >> m;
	lst.resize(n);
	for (int i = 0; i < n; i++) {
		cin >> lst[i];
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (lst[i][j] == 'L') bfs({i, j, 0});
		}
	}
	cout << max_time;
}