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

1. 문제

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

14940번: 쉬운 최단거리

 

2. 알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

 

3. 소스 코드

#include <iostream>
#include <queue>

using namespace std;

int N, M;
int map[1003][1003]; // 지도 정보
int dist[1003][1003]; // 목표지점까지 거리 지도 정보
pair<int, int> goal_pos; // 목표지점 위치

// 방향 배열(상하좌우)
int dy[] = { -1, 0, 1, 0 };
int dx[] = { 0, -1, 0, 1 };

// BFS (너비 우선 탐색) 알고리즘
void bfs()
{
	// 시작점을 queue에 저장 (시작점 : 목표 지점)
	queue<pair<int, int>> q;
	q.push(goal_pos);
	dist[goal_pos.first][goal_pos.second] = 0; // 목표지점의 값 0 저장

	// 더 이상 갈 공간이 없을 떄 까지 무한 반복
	while (!q.empty())
	{
		// 현재 위치
		pair<int, int> cur = q.front();
		q.pop();

		// 방향 배열(dy[], dx[])을 통해 상하좌우 체크
		for (int i = 0; i < 4; i++)
		{
			// 이동할 위치
			pair<int, int> next = { cur.first + dy[i], cur.second + dx[i] };

			if (next.first < 0 || next.first >= N || next.second < 0 || next.second >= M) continue; // 지도 밖으로 벗어났을 경우, 스킵
			if (dist[next.first][next.second] != -1) continue; // 이미 지나간 지역이거나 벽일 경우, 스킵

			// 다음 위치 및 목표 지점까지 거리 저장
			q.push(next);
			dist[next.first][next.second] = dist[cur.first][cur.second] + 1;
		}
	}
}

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

	// 목표지점까지 거리 지도를 전부 -1로 초기화
	fill(&dist[0][0], &dist[1002][1002], -1);

	// 지도 크기 입력
	cin >> N >> M;

	// 지도 정보 입력
	for (int y = 0; y < N; y++)
	{
		for (int x = 0; x < M; x++)
		{
			cin >> map[y][x];

			// 목표지점이면 해당 위치 저장
			if (map[y][x] == 2)
			{
				goal_pos.first = y;
				goal_pos.second = x;
			}

			// 벽이라면 목표지점까지 거리 지도에도 표시
			if (map[y][x] == 0) dist[y][x] = 0;
		}
	}

	// BFS 알고리즘을 통해 목표지점까지 거리 계산
	bfs();

	// 목표지점까지 거리 출력
	for (int y = 0; y < N; y++)
	{
		for (int x = 0; x < M; x++)
			cout << dist[y][x] << " ";

		cout << "\n";
	}

	return 0;
}

 

4. 유용한 문법 / 알고리즘

 1) BFS 알고리즘(너비 우선 탐색)

// BFS (너비 우선 탐색) 알고리즘
void bfs()
{
	// 시작점을 queue에 저장 (시작점 : 목표 지점)
	queue<pair<int, int>> q;
	q.push(goal_pos);
	dist[goal_pos.first][goal_pos.second] = 0; // 목표지점의 값 0 저장

	// 더 이상 갈 공간이 없을 떄 까지 무한 반복
	while (!q.empty())
	{
		// 현재 위치
		pair<int, int> cur = q.front();
		q.pop();

		// 방향 배열(dy[], dx[])을 통해 상하좌우 체크
		for (int i = 0; i < 4; i++)
		{
			// 이동할 위치
			pair<int, int> next = { cur.first + dy[i], cur.second + dx[i] };

			if (next.first < 0 || next.first >= N || next.second < 0 || next.second >= M) continue; // 지도 밖으로 벗어났을 경우, 스킵
			if (dist[next.first][next.second] != -1) continue; // 이미 지나간 지역이거나 벽일 경우, 스킵

			// 다음 위치 및 목표 지점까지 거리 저장
			q.push(next);
			dist[next.first][next.second] = dist[cur.first][cur.second] + 1;
		}
	}
}