취미로 코딩하기

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

이번에 볼 문제는 백준 25895번 문제인 Don't Break the Ice이다.
문제는 아래 링크를 확인하자.

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

입력으로 주어진 칸이 보드에 남아있는지의 여부는 "해당 칸이 있는 행에 모든 칸이 남아있거나 해당 칸이 있는 열에 모든 칸이 남아있는"지의 여부로 확인할 수 있다. 즉, 해당 칸이 있는 행에 있는 어떤 칸이 선택된 적이 있고 해당 칸이 있는 어떤 열이 선택된 적이 있다면 해당 칸은 보드에 남아있지 않다고 판단할 수 있다.

따라서, 각 행과 열의 칸이 선택된 적이 있는지를 관리하는 것으로 문제를 간단히 해결할 수 있다.

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

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

int N, Q;
int row[51], col[51];

int solve() {
	int ret = 0;
	memset(row, 0, sizeof(row));
	memset(col, 0, sizeof(col));

	cin >> N >> Q;
	while (Q--) {
		int r, c; cin >> r >> c;
		if (row[r] && col[c]) ret++;
		else row[r] = col[c] = 1;
	}

	return ret;
}

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

	int T; cin >> T;
	for (int t = 1; t <= T; t++) {
		cout << "Strategy #" << t << ": " << solve() << '\n' << '\n';
	}
}