백준 10164번 격자상의 경로 C++

출처 : https://www.acmicpc.net/problem/10164

 

직사각형의 경로에서 동그라미가 주어지면 그 곳을 거쳐서 오른쪽 밑 끝까지 가고, 주어지지 않으면 그냥 오른쪽 밑 끝까지 가는 경우의 수를 구하는 문제이다.

동그라미의 좌표가 주어지지 않으면 (0, 0)에서 (n-1, m-1) 까지의 경우의 수를 구하고

동그라미의 좌표가 (x, y)라고 주어지면 (0, 0)에서 (x, y) 경우의 수와 (x, y,)에서 (n-1, m-1)까지의 경우의 수를 곱하면 된다. 

동그라미는 좌표가 아닌 숫자로 주어지기 때문에 좌표로 변환해야 한다.

숫자가 k로 주어지면 ( (k - 1) / m , (k - 1) % m ) 의 식을 통해 좌표를 구할 수 있다.

bfs방식을 통해서 경우의 수를 구하였다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <unordered_set>

using namespace std;
typedef long long ll;

int bfs(queue<pair<int, int>> &q, pair<int, int> target) {
	int cnt = 0;
	while (!q.empty()) {
		auto a = q.front();
		q.pop();
		if (a.first == target.first && a.second == target.second) {
			cnt++;
		}
		if (a.first + 1 <= target.first) {
			q.push({ a.first + 1,a.second });
		}
		if (a.second + 1 <= target.second) {
			q.push({ a.first,a.second + 1 });
		}
	}
	return cnt;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, m, k;
	cin >> n >> m >> k;
	vector<vector<int>> v(n, vector<int>(m));
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			v[i][j] = ++cnt;
		}
	}
	int ans = 0;
	queue<pair<int, int>> q;
	q.push({ 0,0 });

	pair<int, int> lastTarget = { n - 1,m - 1 };
	if (k == 0) {
		ans += bfs(q,lastTarget);
	}
	else {
		pair<int, int> firstTarget = { ((k - 1) / m),((k - 1) % m) };
		int ans1 = bfs(q, firstTarget);
		q.push({ firstTarget.first, firstTarget.second });
		int ans2 = bfs(q, lastTarget);
		ans = ans1 * ans2;
	}
	cout << ans;
};