[BOJ] 백준 14940번 쉬운 최단거리 C++

문제

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

14940번: 쉬운 최단거리

풀이

BFS 최단거리로 해결할 수 있었다.

지도를 관리할 2차원 배열인 board와 각 지점의 거리를 관리할 2차원 배열인 dist를 만들어서 지도를 입력받으면서 해당 좌표의 값이 2이면 그 좌표가 탐색의 시작점이므로 startX, startY라는 변수에 담아주었고,

만약 0이 나와 갈 수 없는 땅이라면 처음부터 거리 배열인 dist에 0을 넣어주었다.

이외 해당 좌표의 지도의 값이 1이 나오면 -1을 넣어주었는데 어차피 이 값은 나중에 교체될 값이고, -1이란 특수한 값을 넣어서 방문 처리 여부도 확인할 수 있기에 -1을 넣어주었다.

이후에는 시작 좌표를 기반으로 BFS를 수행하여 범위의 밖으로 나가는 것을 체크, 이미 방문했거나(dist[nx][ny] != -1), 갈 수 없는 땅인지(board[nx][ny] == 0) 체크해 주면서 각 지점까지의 거리를 갱신해 주면 각 지점까지의 거리가 담긴 dist배열을 완성할 수 있고, 이후 출력해 주면 문제를 해결할 수 있다.

코드

#include <iostream>
#include <queue>
#define x first
#define y second

using namespace std;

int n, m;
int startX, startY;
const int dx[4] = { 1,0,-1,0 };
const int dy[4] = { 0,1,0,-1 };
int board[1001][1001];
int dist[1001][1001];
queue<pair<int, int>> q;

void initialValueSet();
void bfs();
void printResult();

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	initialValueSet();
	bfs();
	printResult();
}

void bfs()
{
	q.push({ startX, startY });

	while (!q.empty())
	{
		auto cur = q.front();
		q.pop();

		for (int dir = 0; dir < 4; dir++)
		{
			int nx = cur.x + dx[dir];
			int ny = cur.y + dy[dir];

			if (nx < 0 || nx >= n || ny < 0 || ny >= m)
			{
				continue;
			}
			if (board[nx][ny] == 0 || dist[nx][ny] != -1)
			{
				continue;
			}

			q.push({ nx, ny });
			dist[nx][ny] = dist[cur.x][cur.y] + 1;
		}
	}
}

void initialValueSet()
{
	cin >> n >> m;

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			cin >> board[i][j];
			if (board[i][j] == 1)
			{
				dist[i][j] = -1;
			}
			else
			{
				if (board[i][j] == 2)
				{
					startX = i;
					startY = j;
				}
				dist[i][j] = 0;
			}
		}
	}
}

void printResult()
{
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			cout << dist[i][j] << " ";
		}
		cout << "\n";
	}
}