취미로 코딩하기

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

이번에 볼 문제는 백준 30679번 문제인 별 가두기이다.
문제는 아래 링크를 확인하자.

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

1열에 있는 각 칸에 별을 둘 때 격자 밖으로 빠져나가지 않는 칸의 수를 세는 문제이다.

각 칸으로부터 40001회 이동한 뒤에서 격자 안에 있다면 별은 격자를 빠져나가지 않을 것임을 관찰하자. 비둘기집의 원리에 의해 위 이동과정에는 같은 칸에서 같은 방향을 바라보고 있는 상황이 반드시 존재하므로 움직임이 반복됨을 알 수 있기 때문이다.

따라서 1열의 각 칸에 별을 올려두고 40001회씩 이동을 시도하는 시뮬레이션을 통해 문제를 해결할 수 있다.

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

#include <iostream>
using namespace std;

int R, C;
int A[100][100];
int dr[4] = {0,1,0,-1};
int dc[4] = {1,0,-1,0};
int ans;
int acnt[100];

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 r = 0; r < R; r++) {
		int rr = r, cc = 0; bool chk = 1;
		for (int k = 0; k < 40001; k++) {
			int rval = dr[k % 4] * A[rr][cc];
			int cval = dc[k % 4] * A[rr][cc];
			rr += rval, cc += cval;
			if (rr < 0 || rr >= R || cc < 0 || cc >= C) {
				chk = 0;
				break;
			}
		}
		if (chk) ans++, acnt[r] = 1;
	}

	cout << ans << '\n';
	for (int r = 0; r < R; r++) {
		if (acnt[r]) cout << r + 1 << ' ';
	}
}