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

문제

[C++] 백준 14940: 쉬운 최단거리 SILVER 1
https://www.acmicpc.net/problem/14940

 

---

 

접근 방법

이 문제는 시작점(값이 2인 위치)에서 각 칸까지의 최단 거리를 구하는 문제이다.
이동은 상하좌우로 가능하며, 값이 1인 칸만 이동할 수 있고 0은 이동할 수 없다.

최단 거리를 구하는 문제이므로 BFS(너비 우선 탐색) 를 사용했다.

 

핵심 아이디어:

1. 시작점(2)의 좌표를 먼저 찾는다.
2. BFS를 이용해 사방 탐색을 진행한다.
3. 이동 가능한 칸(값이 1)만 큐에 넣는다.
4. 현재 칸의 거리 + 1을 다음 칸의 거리로 저장한다.

BFS는 먼저 방문한 경로가 곧 최단 거리이므로 별도의 최단 거리 비교 없이도 정확한 값이 저장된다.

결과 배열 ret은 -1로 초기화하여 도달하지 못한 칸을 구분할 수 있도록 했다.

 

구현 시 주의할 점

• 결과 배열 초기화
  • ret을 0으로 초기화하면 틀린다.
    • 원래 값이 0인 칸 → 출력 0
    • 원래 값이 1인데 도달 불가 → 출력 -1
• 시작점은 반드시 거리 0으로 설정해야 한다.
• 방문 체크 위치
  • 큐에 넣는 순간 방문 체크를 해야 중복으로 큐에 들어가는 것을 막을 수 있다.

 

---

 

코드

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

vector<vector<int>> vect;
vector<vector<int>> ret;
vector<vector<bool>> visited;
int n, m;
int dy[4] = { 0,1,0,-1 };
int dx[4] = { 1,0,-1,0 };

void BFS(int yy, int xx)
{
	queue<pair<int, int>> Q;
	Q.push(make_pair(yy, xx));
	visited[yy][xx] = true;
	ret[yy][xx] = 0;

	int cnt = 0;
	while (!Q.empty())
	{
		int now[2] = { Q.front().first, Q.front().second };
		Q.pop();

		for (int i = 0; i < 4; i++)
		{
			int y = now[0] + dy[i];
			int x = now[1] + dx[i];

			if (y < 0 || n <= y || x < 0 || m <= x
				|| visited[y][x] == true || vect[y][x] == 0)
				continue;

			Q.push(make_pair(y, x));
			visited[y][x] = true;
			ret[y][x] = ret[now[0]][now[1]] + 1;
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> m;
	vect.resize(n, vector<int>(m));
	ret.resize(n, vector<int>(m, -1));
	visited.resize(n, vector<bool>(m, false));

	int startY = 0, startX = 0;
	for (int y = 0; y < n; y++)
	{
		for (int x = 0; x < m; x++)
		{
			cin >> vect[y][x];

			if (vect[y][x] == 2)
			{
				startY = y;
				startX = x;
			}
			if (vect[y][x] == 0)
				ret[y][x] = 0;
		}
	}
	BFS(startY, startX);

	for (int y = 0; y < n; y++)
	{
		for (int x = 0; x < m; x++)
		{
			cout << ret[y][x] << ' ';
		}
		cout << '\n';
	}

	return 0;
}