[BAEKJOON] 14940번 쉬운 최단거리

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

14940번: 쉬운 최단거리

 

문제조건

 

1. 목표지점부터 모든 지점에 대해서 목표지점까지의 거리 구하기

너무 당연하게 BFS로 풀이를 시작했다.

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

int n, m, map[1001][1001], visited[1001][1001], dist[1001][1001];
int dy[] = { -1, 0, 1, 0 };
int dx[] = { 0, -1, 0, 1 };

void bfs(int sy, int sx) {
	queue<pair<int, int>> q;
	q.push({ sy, sx });
	visited[sy][sx] = 1;
	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (ny < 0 || ny >= n || nx < 0 || nx >= m) continue;
			if (!visited[ny][nx] && map[ny][nx]) {
				q.push({ ny, nx });
				visited[ny][nx] = 1;
				dist[ny][nx] = dist[y][x] +1;
			}
		}
	}
}

int main(){
	cin >> n >> m;
	int sx = 0, sy = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> map[i][j];
			if (map[i][j] == 2) {
				sy = i;
				sx = j;
			}
		}
	}

	bfs(sy, sx);

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

너무 쉬운데?

는 대참사,,,

문제를 계속 살펴봤다,, 아무리 생각해도 틀린게 없는데 그냥 BFS로 푸는 거 아닌가?

맞긴 맞는데,  원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -1을 출력한다. 이 부분을 간과 했던 것이다,,,

 

 

따라서 visited배열이 1로 바뀌지 않은 즉, 입력 map은 1로 받았지만, 방문하지 못한 곳을 따로 조건을 두어 출력했다.

 

#include <iostream>
#include <queue>
#include <string.h>
using namespace std;

int n, m, map[1001][1001], visited[1001][1001], dist[1001][1001];
int dy[] = { -1, 0, 1, 0 };
int dx[] = { 0, -1, 0, 1 };

void bfs(int sy, int sx) {
	queue<pair<int, int>> q;
	q.push({ sy, sx });
	visited[sy][sx] = 1;
	map[sy][sx] = 0;

	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (ny < 0 || ny >= n || nx < 0 || nx >= m) continue;
			if (!visited[ny][nx] && map[ny][nx]) {
				q.push({ ny, nx });
				visited[ny][nx] = 1;
				dist[ny][nx] = dist[y][x] +1;
			}
		}
	}
}

int main(){
	cin >> n >> m;
	int sx = 0, sy = 0;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> map[i][j];
			if (map[i][j] == 2) {
				sy = i;
				sx = j;
				dist[i][j] = 0;
			}
		}
	}

	bfs(sy, sx);

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (map[i][j] == 1 && visited[i][j] == 0) cout << -1 << " ";
			else cout << dist[i][j] << " ";
		}
		cout << '\n';
	}
}

 

성공,,!

 

문제를 풀때 무턱대고 알고리즘 부터 찾아보려고 하는 거같은데, 앞으로는 문제를 꼼꼼히 읽어봐야겠다.