[BOJ 5913 // C++] 준규와 사과

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

 

이번에 볼 문제는 백준 5913번 문제인 준규와 사과이다.
문제는 아래 링크를 확인하자.

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

5913번: 준규와 사과

5행 5열의 농장에서 좌상단 칸으로부터 우하단 칸까지 모든 사과나무를 한번씩 방문하면서 가는 경로의 수를 구하는 문제이다.

 

농장의 크기가 작고, 농장을 그래프로 나타냈을 때 에지의 개수가 많지 않으므로(많아야 한 사과나무 주변에 있는 사과나무는 상하좌우 넷 뿐임을 생각하자) 그래프 위에서의 완전탐색을 통해 문제를 해결할 수 있다.

 

도착점에 도착했을 때 모든 사과나무를 들리고 왔는지 확인하기 위하여 방문한 칸 수를 변수로 이용하였다.

 

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

#include <iostream>
using namespace std;

int N = 5, total;
bool visited[22][22];

int dr[4] = { 1,-1,0,0 };
int dc[4] = { 0,0,1,-1 };

int cnt = 0;
void dfs(int curr, int curc, int visitcnt) {
	if (curr == N - 1 && curc == N - 1) {
		if (visitcnt == total) cnt++;
	}
	else {
		for (int i = 0; i < 4; i++) {
			int rr = curr + dr[i], cc = curc + dc[i];
			if (rr < 0 || rr >= N || cc < 0 || cc >= N) continue;
			if (visited[rr][cc]) continue;
			visited[rr][cc] = 1;
			dfs(rr, cc, visitcnt + 1);
			visited[rr][cc] = 0;
		}
	}
}

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

	int K;  cin >> K;
	total = 25 - K;

	while (K--) {
		int x, y; cin >> x >> y; x--; y--;
		visited[x][y] = 1;
	}

	visited[0][0] = 1;
	dfs(0, 0, 1);

	cout << cnt;
}