취미로 코딩하기

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

이번에 볼 문제는 백준 23352번 문제인 방탈출이다.
문제는 아래 링크를 확인하자.

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

어떤 한 칸으로부터 다른 모든 칸까지의 최단경로를 구하는 것은 전체 그래프에 대하여 BFS를 한 번 시행하는 것으로 해낼 수 있다. 이 시간복잡도는 \(O(RC)\)이다.

모든 두 칸의 쌍에 대하여 두 칸을 잇는 최단경로의 길이는 위와 같은 탐색을 모든 칸에서 \(O(RC)\)회 시작해보는 것으로 접근 가능하므로, 가장 긴 최단경로의 길이를 갖는 경로 중 양 끝 칸의 수의 합이 가장 큰 경우는 \(O(R^2C^2)\)으로 구할 수 있다. \(R\)과 \(C\)의 값이 충분히 작으므로 이는 시간 내에 충분히 동작한다.

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

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

int R, C;
int board[52][52];
int dist[52][52];
int adist, ans;
int dr[4] = {0,0,1,-1};
int dc[4] = {1,-1,0,0};
queue<pair<int, int>> que;
void bfs(int sR, int sC) {
	memset(dist, 0, sizeof(dist));
	que.push(make_pair(sR, sC));
	dist[sR][sC] = 1;
	while (!que.empty()) {
		int r = que.front().first, c = que.front().second; que.pop();
		if (dist[r][c] > adist) adist = dist[r][c], ans = board[sR][sC] + board[r][c];
		else if (dist[r][c] == adist) ans = max(ans, board[sR][sC] + board[r][c]);
		for (int i = 0; i < 4; i++) {
			int rr = r + dr[i], cc = c + dc[i];
			if (!board[rr][cc] || 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++) {
			cin >> board[r][c];
		}
	}

	for (int r = 1; r <= R; r++) {
		for (int c = 1; c <= C; c++) {
			if (board[r][c]) bfs(r, c);
		}
	}

	cout << ans;
}