DeveloperOC
🔗 쉬운 최단거리
https://www.acmicpc.net/problem/14940
📌 문제 요약
지도가 주어지면 모든 지점에 대해서 목표지점까지의 거리를 구하여라.
문제를 쉽게 만들기 위해 오직 가로와 세로로만 움직일 수 있다고 하자.입력: 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000)
다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이다. 입력에서 2는 단 한개이다. **
**출력: 각 지점에서 목표지점까지의 거리를 출력한다. 원래 갈 수 없는 땅인 위치는 0을 출력하고, 원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -1을 출력한다.
💡 접근 방법
queue를 사용한 bfs알고리즘 방식으로 문제를 풀어냈다.
queue에 목표지점을 저장한 뒤 주변 네방향의 좌표가 1인 경우 push 해준다.
네방향의 거리는 현재 거리에서 1을 더한것과 같기 때문에 push해줌과 동시에 더해준다.
⚠️ 처음에 했던 실수
💻 코드
#include <iostream>
#include <cmath>
#include <utility>
#include <queue>
using namespace std;
int n, m;
int map[1001][1001];
int dis[1001][1001];
int offset[4][2] =
{
{1,0},
{0,1},
{-1,0},
{0,-1},
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
pair<int, int> fin;
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)
{
fin.first = i;
fin.second = j;
}
}
}
queue<pair<int, int>> q;
q.push(fin);
int cnt = 0;
dis[fin.first][fin.second] = cnt;
while(q.size() != 0)
{
pair<int, int> f = q.front();
q.pop();
for(int i = 0; i < 4; ++i)
{
int nexR = f.first + offset[i][0];
int nexC = f.second + offset[i][1];
if(nexR < 0 || nexC < 0 || nexR >= n || nexC >= m)
continue;
if(fin.first == nexR && fin.second == nexC)
continue;
if(map[nexR][nexC] == 0)
{
dis[nexR][nexC] = 0;
continue;
}
if(dis[nexR][nexC] > 0)
continue;
dis[nexR][nexC] = dis[f.first][f.second] + 1;
q.push(make_pair(nexR, nexC));
}
}
for(int i = 0; i < n; ++i)
{
for(int j = 0; j < m; ++j)
{
if(dis[i][j] == 0 && map[i][j] == 1)
{
dis[i][j] = -1;
}
cout << dis[i][j] << " ";
}
cout << '\n';
}
return 0;
}