취미로 코딩하기

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

이번에 볼 문제는 백준 5558번 문제인 チーズ (Cheese)이다.
문제는 아래 링크를 확인하자.

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

S에서 1, 1에서 2, 2에서 3, ..., N-1에서 N까지의 최단경로를 각각 BFS등을 통해 구해내고, 이들을 더해 문제를 해결할 수 있다. S의 위치에 "0"이 적혀있는 것으로 생각하면 경로를 구해야하는 모든 쌍을 수식 하나로 편하게 나타낼 수 있어 편리하다.

주어지는 격자판의 크기가 최대100만이고, 따라서 이 격자판을 그래프로 표현했을 때의 노드 수와 에지 수의 합이 1000만보다 작으므로 BFS를 10번 하는 것은 (지나치게 비효율적으로 구현하지 않는다면) 시간제한 내로 충분히 돌아갈 수 있다고 생각할 수 있다.

상하좌우 칸의 이동은 아래와 같이 dr배열과 dc배열을 이용하면 편하게 구현이 가능하다.

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

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

int R, C, N;
string board[1000];

int points[10][2];
int dist[1000][1000];
int dr[4] = { 1,-1,0,0 };
int dc[4] = { 0,0,1,-1 };

int bfs(int i) {
	memset(dist, 0, sizeof(dist));
	queue<pair<int, int>> que;
	que.push(make_pair(points[i][0], points[i][1]));
	dist[points[i][0]][points[i][1]] = 1;

	while (!que.empty()) {
		int r = que.front().first, c = que.front().second;
		que.pop();
		for (int k = 0; k < 4; k++) {
			int rr = r + dr[k], cc = c + dc[k];
			if (rr < 0 || rr >= R || cc < 0 || cc >= C) continue;
			if (dist[rr][cc] || board[rr][cc] == 'X') continue;
			dist[rr][cc] = dist[r][c] + 1;
			que.push(make_pair(rr, cc));
		}
	}

	return dist[points[i + 1][0]][points[i + 1][1]] - 1;
}

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

	cin >> R >> C >> N;
	for (int r = 0; r < R; r++) {
		string& s = board[r];
		cin >> s;
		for (int c = 0; c < C; c++) {
			if (s[c] != '.' && s[c] != 'X') {
				if (s[c] == 'S') points[0][0] = r, points[0][1] = c;
				else points[s[c] - '0'][0] = r, points[s[c] - '0'][1] = c;
			}
		}
	}
	
	int ans = 0;
	for (int i = 0; i < N; i++) {
		ans += bfs(i);
	}

	cout << ans;
}