취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 14940번 문제인 쉬운 최단거리이다.
문제는 아래 링크를 확인하자.

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

2가 써져있는 칸에서부터 시작하여 상하좌우 한칸씩을 방문하는 bfs를 통해 문제를 해결하자.

전체 배열 바깥쪽 둘레에 0을 한줄씩 더 깔아두면 편한 구현이 가능하다.

아래의 코드에서의 dr 및 dc와 같은 배열을 이용하면 상하좌우 방문을 편하게 구현할 수 있다.

입력에서 0으로 주어진 칸은 0, 1로 주어졌으나 방문하지 못하는 칸은 -1을 출력해야 함에 유의하자.

아래는 제출한 소스코드이다.

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

int R, C;
int arr[1002][1002];
int dist[1002][1002];
int dr[4] = { 1,-1,0,0 };
int dc[4] = { 0,0,1,-1 };

queue<pair<int, int>> que;

void bfs() {
	while (!que.empty()) {
		int r = que.front().first, c = que.front().second;
		que.pop();
		for (int i = 0; i < 4; i++) {
			int rr = r + dr[i], cc = c + dc[i];
			if (arr[rr][cc] == 0 || dist[rr][cc]) continue;
			dist[rr][cc] = dist[r][c] + 1;
			que.push(make_pair(rr, cc));
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> R >> C;
	for (int r = 1; r <= R; r++) {
		for (int c = 1; c <= C; c++) {
			int& cur = arr[r][c];
			cin >> cur;
			if (cur == 2) dist[r][c] = 1, que.push(make_pair(r, c));
		}
	}

	bfs();

	for (int r = 1; r <= R; r++) {
		for (int c = 1; c <= C; c++) {
			if (arr[r][c] == 0) cout << 0 << ' ';
			else cout << dist[r][c] - 1 << ' ';
		}
		cout << '\n';
	}
}