[백준 14940][💛5] 쉬운 최단거리 (BFS)

🚀 난이도

💛 골드 5

🚀 문제

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

🚀 내 풀이 ⭕

정말 기본적인 BFS 문제!

• 문제에서 목표지점이라고 주어진 부분을 시작점이라고 생각한다.
  • 하나의 시작점으로부터 모든 지점까지의 거리를 구하는 BFS
• 도달할 수 없는 위치는 -1로 출력을 해야 한다.
  • if (Dist[i][j] == 0 && Map[i][j] == 1)
    • 갈 수 있는 곳임에도 불구하고 Map[i][j] == 1, BFS 결과 목표지점으로부터 거리가 0 인 곳은 갈 수 없는 곳이나 마찬가지이다.

#include <bits/stdc++.h>

using namespace std;

int N, M;
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
struct Pos { int x, y; };
int Map[1000][1000];
int Dist[1000][1000];

void bfs(Pos dest) {  // 매개변수 출발지. (문제에선 목표지점으로 주어져서 dest 로 이름 짓긴했지만..)
	queue<Pos> q;
	vector<vector<bool>> visited(N, vector<bool>(M));

	q.push(dest);
	Dist[dest.x][dest.y] = 0;
	visited[dest.x][dest.y] = true;

	while (!q.empty()) {
		Pos now = q.front();
		q.pop();

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

			if (nextX < 0 || nextX >= N || nextY < 0 || nextY >= M) continue;
			if (Map[nextX][nextY] == 0) continue;
			if (visited[nextX][nextY]) continue;

			q.push({ nextX, nextY });
			Dist[nextX][nextY] = Dist[now.x][now.y] + 1;
			visited[nextX][nextY] = true;
		}
	}
}

int main() {
	//freopen("input.txt", "r", stdin);
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	Pos dest;
	cin >> N >> M;
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < M; ++j) {
			cin >> Map[i][j];
			if (Map[i][j] == 2) {
                // 출발지 저장
				dest.x = i;
				dest.y = j;
			}
		}
	}

	bfs(dest);
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < M; ++j) {
			if (Dist[i][j] == 0 && Map[i][j] == 1)
				cout << -1 << ' ';
			else
				cout << Dist[i][j] << ' ';
		}	
		cout << '\n';
	}
}

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

BOJ 카테고리 내 다른 글 보러가기