BOJ 14940 (쉬운 최단거리)

• 문제
  지도가 주어지면 모든 지점에 대해서 목표지점까지의 거리를 구하여라.
  문제를 쉽게 만들기 위해 오직 가로와 세로로만 움직일 수 있다고 하자.
  
  
• 입력
  지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000)
  
  다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이다. 입력에서 2는 단 한개이다.
  
  
• 출력
  각 지점에서 목표지점까지의 거리를 출력한다. 원래 갈 수 없는 땅인 위치는 0을 출력하고, 원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -1을 출력한다.

#include<iostream>
#include<queue>

using namespace std;
int column, row;
int ground[1001][1001];
bool visited[1001][1001];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
int startY, startX;

void fast_io() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
}

void input() {
	cin >> column >> row;
	for (int i = 0; i < column; i++) {
		for (int j = 0; j < row; j++) {
			cin >> ground[i][j];
			if (ground[i][j] == 2) {
				startY = i;
				startX = j;
			}
		}
	}
}

void bfs(int y, int x) {
	queue<pair<int, int>> q;
	q.push({ y,x });
	visited[y][x] = true;

	while (!q.empty()) {
		int currentY = q.front().first;
		int currentX = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++)
		{
			int delta_Y = currentY + dy[i];
			int delta_X = currentX + dx[i];

			if ((delta_Y < 0 || delta_Y > column || delta_X < 0 || delta_X > row)) {
				continue;
			}

			if (!visited[delta_Y][delta_X] && ground[delta_Y][delta_X] != 0)
			{
				visited[delta_Y][delta_X] = true;
				ground[delta_Y][delta_X] = ground[currentY][currentX] + 1;
				q.push({ delta_Y,delta_X });
			}
		}
	}
}

void print() {
	for (int i = 0; i < column; i++)
	{
		for (int j = 0; j < row; j++)
		{
			if (!visited[i][j] && ground[i][j] == 1)
			{
				ground[i][j] = -1;
			}

			cout << ground[i][j] << ' ';
		}
		cout << '\n';
	}
}

int main() {
	fast_io();
	input();
	ground[startY][startX] = 0;
	bfs(startY, startX);
	print();
	return 0;
}

   그래프에서 BFS를 이용하여 푸는 문제이다. 처음에 가로의 크기, 세로의 크기를 잘못 이해해서 직사각형 배열을 뽑는다면 가로 세로 길이 반대로 출력값이 나왔다..

위의 풀이에서는
column : 세로의 크기 -> 행의 길이 , row : 가로의 크기 : 열의 길이로 이해하면 된다.

입력 값에서 2인 좌표를 따기 위해 startY, startX에 저장해주고 BFS를 수행하였다.

도달할 수 없는 지점에 대한 처리는 그 지점은 visit 한 적이 없을 것이고 땅의 숫자 값이 1이 유지됨을 이용해서 출력 직전에 값을 변경해주면 된다.

시간 복잡도 : O(MN)

숏코딩

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <tuple>

using namespace std;

int main() {
  int n, m;
  cin >> n >> m;
  vector<vector<int>> map(n, vector<int>(m)), result(map);
  queue<tuple<int, int, int>> q;
  for(int i = 0; i < n; i++)
    for(int j = 0; j < m; j++) {
      cin >> map[i][j];
      result[i][j] = -!!map[i][j];
      if(map[i][j] == 2)
        q.emplace(i, j, 0);
    }
  while(!q.empty()) {
    auto [y, x, d] = q.front();
    q.pop();
    if(result[y][x] != -1)
      continue;
    result[y][x] = d++;
    if(y)
      q.emplace(y - 1, x, d);
    if(x)
      q.emplace(y, x - 1, d);
    if(y != n - 1)
      q.emplace(y + 1, x, d);
    if(x != m - 1)
      q.emplace(y, x + 1, d);
  }
  for(const auto &row: result) {
    for(int x: row)
      cout << x << " ";
    cout << "\n";
  }
}

이해는 잘 안되지만 신기한 풀이라서 나중에 다시 볼때 공부해야겠다