취미로 코딩하기

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

이번에 볼 문제는 백준 23973번 문제인 표적지 옮기기이다.
문제는 아래 링크를 확인하자.

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

표적지에는 10을 나타내는 칸이 유일하게 존재한다. 또한 각 점수를 나타내는 영역에 정확히 한 발씩 명중했는지를 확인해야한다. 이와 같은 조건을 만족하게 표적지를 놓을 때 하나뿐인 10을 나타내는 칸은 명중한 칸이어야한다.

따라서 사격판의 모든 칸에 대하여 해당 칸이 명중한 칸인지를 살피고(O(NM)), 만약 명중한 칸이면 그 칸을 표적지의 중심으로 위치시켰을 때 조건을 만족하는지 체크하는 것으로 문제를 해결할 수 있다.

10점을 원점으로 생각할 때, 점 (X,Y)와 원점 사이 거리를 max(X,Y)로 정의하면 어떤 일이 일어나는지 관찰한다면 구현을 더욱 편리하게 할 수 있게 된다.

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

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

string board[2500];
int cnt[10];

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

	int R, C; cin >> R >> C;
	for (int r = 0; r < R; r++) cin >> board[r];

	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			if (board[r][c] == '1') {
				memset(cnt, 0, sizeof(cnt));
				int rowL = max(r - 9, 0), rowR = min(r + 10, R);
				int colL = max(c - 9, 0), colR = min(c + 10, C);
				for (int rr = rowL; rr < rowR; rr++) {
					for (int cc = colL; cc < colR; cc++) {
						if (board[rr][cc] == '1') {
							cnt[max(abs(r - rr), abs(c - cc))]++;
						}
					}
				}
				bool chk = 1;
				for (int i = 0; i < 10; i++) {
					if (cnt[i] != 1) chk = 0;
				}

				if (chk) {
					cout << r << ' ' << c;
					return 0;
				}
			}
		}
	}

	cout << -1;
}