취미로 코딩하기

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

이번에 볼 문제는 백준 11379번 문제인 Avoider이다.

문제는 아래 링크를 확인하자.

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

Self-Avoiding Walk의 경우의 수를 구하는 문제이다.

단순하게 모든 경우의 수를 시뮬레이션하는 프로그램을 작성해 돌려도 글쓴이 기준 2시간 이내에 경우의 수를 구할 수 있었다.

구한 경우의 수를 이용하여 간단히 문제를 해결하자.

아래는 Self-Avoiding Walk의 경우의 수를 구하기 위해 사용한 소스코드이다.

#include <iostream>
using namespace std;
typedef long long ll;

ll ans[30];
ll visited[31][31];

void func(int r, int c, int cnt) {
	ans[cnt]++;
	visited[r][c] = 1;
	if (cnt < 28) {
		if (!visited[r - 1][c]) func(r - 1, c, cnt + 1);
		if (!visited[r + 1][c]) func(r + 1, c, cnt + 1);
		if (!visited[r][c - 1]) func(r, c - 1, cnt + 1);
		if (!visited[r][c + 1]) func(r, c + 1, cnt + 1);
	}
	visited[r][c] = 0;
}

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

	for (int i = 0; i < 31; i++) visited[i][0] = visited[0][i] = 1;
	visited[1][1] = 1;

	func(1, 2, 1);

	for (int i = 1; i < 29; i++) cout << ans[i] << ',';
}