백준 25416 빠른 숫자 탐색 (c++) : 피너클

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

25416번: 빠른 숫자 탐색

bfs문제다.

for (int i = 0; i < 5; i++)
	for (int j = 0; j < 5; j++) {
		cin >> map[i][j];
		visited[i][j] = false;
	}
cin >> r >> c;
cout << bfs() << endl;

값을 입력받으며 visited를 false로 초기화 해주고 bfs를 돌리면 된다.

int bfs() {
	queue<pair<int, pair<int, int>>> q;
	q.push({ 0, {r, c} });
	visited[r][c] = true;

q에는 {이동 횟수, {현재 위치 y, 현재 위치 x}}가 들어간다.

처음엔 이동 횟수가 0이니 0과 함께 넣어주고 visited[r][c]를 true로 바꾼다.

	while (!q.empty()) {
		int y = q.front().second.first;
		int x = q.front().second.second;
		int time = q.front().first;
		q.pop();

q가 비어있지 않은 동안 반복한다.

q앞의 모든 값들을 꺼내고 pop한다.

		if (map[y][x] == 1) return time;

만약 목표 지점에 도달했다면 현재 까지의 횟수를 반환한다.

		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (0 <= ny && ny <= 4 && 0 <= nx && nx <= 4) {
				if (!visited[ny][nx] && map[ny][nx] != -1) {
					visited[ny][nx] = true;
					q.push({ time + 1, {ny, nx} });
				}
			}
		}
	}
	return -1;
}

그후 현재 위치에서 4방향을 확인하며

범위 안에 들어있고 방문하지 않았으며 -1이 아니면 다음 위치를 방문한다.

만약 bfs를 전부 돌렸는데도 1에 도달하지 못했다면 -1을 반환한다.

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

int dx[] = { 0, 1, 0, -1 };
int dy[] = { 1, 0, -1, 0 };
bool visited[5][5];
int map[5][5];
int r, c;

int bfs() {
	queue<pair<int, pair<int, int>>> q;
	q.push({ 0, {r, c} });
	visited[r][c] = true;
	while (!q.empty()) {
		int y = q.front().second.first;
		int x = q.front().second.second;
		int time = q.front().first;
		q.pop();
		if (map[y][x] == 1) return time;
		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (0 <= ny && ny <= 4 && 0 <= nx && nx <= 4) {
				if (!visited[ny][nx] && map[ny][nx] != -1) {
					visited[ny][nx] = true;
					q.push({ time + 1, {ny, nx} });
				}
			}
		}
	}
	return -1;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	for (int i = 0; i < 5; i++)
		for (int j = 0; j < 5; j++) {
			cin >> map[i][j];
			visited[i][j] = false;
		}
	cin >> r >> c;
	cout << bfs() << endl;
}

전체코드다.