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

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

14940번: 쉬운 최단거리

---

알고리즘 분류

 

BFS(너비 우선 탐색)

 

---

 

해설

 

 

#include <iostream>
#include <queue>
using namespace std;
int main() {
	int n, m;
	cin >> n >> m;
	int** map = new int* [n];
	bool** visit = new bool* [n];
	for (int i = 0; i < n; i++) {
		map[i] = new int[m];
		visit[i] = new bool[m];
	}
		

	int target_x, target_y; // 목표지점 좌표

	// map 입력
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> map[i][j];
			visit[i][j] = 0;
			if (map[i][j] == 2) {
				target_x = i;
				target_y = j;
				map[i][j] = 0;
			}
		}
	}

	int dx[4] = { 0,0,-1,1 };
	int dy[4] = { -1,1,0,0 };
	
	queue<pair<int, int>> q;
	q.push(make_pair(target_x, target_y));
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int ny = dy[i] + y;
			int nx = dx[i] + x;

			if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
				if (visit[nx][ny] == 0) {
					visit[nx][ny] = 1;
					if (map[nx][ny] == 0) // 못 지나가는 곳
						continue;
					else {
						map[nx][ny] = map[x][y] + 1;
						q.push(make_pair(nx, ny));
					}
				}
			}
		}
	}
	// 예외 처리 및 출력
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (visit[i][j] == 0) {
				if (map[i][j] != 0) 
					map[i][j] = -1;
			}
			cout << map[i][j] << " ";
		}
		cout << "\n";
	}
}

 

일반적인 BFS 알고리즘입니다

해당 문제에서는 벽이 아닌 곳(1)에서 목표지점까지 갈 수 없다면 -1로

표현하는 것이 특이했습니다.

 

그래서 일반적인 BFS 구문을 통해

방문하지 않은 좌표가 벽이 아니었다면 -1로 바꿔주는 예외 처리를

해준다면 정답으로 나옵니다

 

질문 게시판을 보니깐 보통 nx, ny(움직일 다음 좌표)에서

행렬을 바꿔 기입하는 경우가 많은데 이 점을 살펴보시는 것도 좋겠습니다