취미로 코딩하기

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

이번에 볼 문제는 백준 17086번 문제인 아기 상어 2이다.
문제는 아래 링크를 확인하자.

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

주어진 모든 \(NM\)개의 칸에 대하여, 상어가 있는 \(O(NM)\)개의 칸과의 거리를 각각 확인해 안전거리를 계산하고, 그 중 가장 큰 값을 계산해 문제를 해결하자. 두 칸 사이의 안전거리는 (행의 차이)와 (열의 차이) 중 더 큰 값과 같다.

위와 같은 풀이의 시간복잡도는 \(O(N^2M^2)\)으로, \(N\)과 \(M\)이 최대 50이므로 이는 문제를 해결하기에 충분한 시간복잡도임을 알 수 있다.

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

#include <iostream>
using namespace std;

int R, C;
int A[50][50];
int ans;

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

	cin >> R >> C;
	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			cin >> A[r][c];
		}
	}
	for (int rr = 0; rr < R; rr++) {
		for (int cc = 0; cc < C; cc++) {
			int mn = 1000000007;
			for (int r = 0; r < R; r++) {
				for (int c = 0; c < C; c++) {
					if (A[r][c]) mn = min(mn, max(abs(r - rr), abs(c - cc)));
				}
			}
			ans = max(ans, mn);
		}
	}

	cout << ans;
}