백준 25513번 빠른 오름차순 숫자 탐색

문제 링크입니다: https://www.acmicpc.net/problem/25513

25513번: 빠른 오름차순 숫자 탐색

전형적인 BFS 문제에서 1 ~ 6이 적힌 칸은 여러 번 밟을 수 있는 조건이 하나 추가된 문제였습니다. 

 

알고리즘은 아래와 같습니다.

1. 1부터 6까지 순차적으로 탐색해야 하므로 반복문을 돌리며 BFS를 수행합니다.

2. 현재 위치 {r, c}에서 탐색하는 숫자가 있는 칸까지 도달할 때까지 BFS를 수행하고 만약 해당 숫자까지 갈 수 없으면 -1을 출력하고 프로그램을 종료합니다.

3. 1부터 6까지 탐색 완료했을 경우 총 움직인 거리를 출력해줍니다.

 

	#include <iostream>
	#include <queue>
	#include <algorithm>
	using namespace std;
	const int MAX = 5;
	typedef struct
	{
	int y, x;
	} Dir;
	Dir moveDir[4] = { {-1, 0}, {1, 0}, {0, 1}, {0, -1} };
	int dist[MAX][MAX];
	bool isOutOfBounds(int y, int x)
	{
	return y < 0 || y >= MAX || x < 0 || x >= MAX;
	}
	void initDist()
	{
	for (int y = 0; y < MAX; y++)
	{
	for (int x = 0; x < MAX; x++)
	{
	dist[y][x] = -1;
	}
	}
	}
	int main(void)
	{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int board[MAX][MAX];
	for (int y = 0; y < MAX; y++)
	{
	for (int x = 0; x < MAX; x++)
	{
	cin >> board[y][x];
	}
	}
	int r, c;
	cin >> r >> c;
	int answer = 0;
	for (int target = 1; target <= 6; target++)
	{
	queue <pair<int, int>> q;
	q.push({ r, c });
	initDist();
	dist[r][c] = 0;
	bool targetArrived = false;
	while (!q.empty())
	{
	int y = q.front().first;
	int x = q.front().second;
	q.pop();
	if (board[y][x] == target)
	{
	answer += dist[y][x];
	r = y;
	c = x;
	targetArrived = true;
	break;
	}
	for (int k = 0; k < 4; k++)
	{
	int nextY = y + moveDir[k].y;
	int nextX = x + moveDir[k].x;
	if (isOutOfBounds(nextY, nextX)
	|| board[nextY][nextX] == -1)
	{
	continue;
	}
	if (dist[nextY][nextX] != -1)
	{
	continue;
	}
	dist[nextY][nextX] = dist[y][x] + 1;
	q.push({ nextY, nextX });
	}
	}
	if (targetArrived == false)
	{
	cout << -1 << "\n";
	return 0;
	}
	}
	cout << answer << "\n";
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub

 

개발환경:Visual Studio 2022

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~