[C/C++] 백준 - 18290번 : NM과 K(1)

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

18290번: NM과 K (1)

N과 M을 응용한 문제로 2차원 배열에서 사용해야한다.

인접한 구간끼리는 합을 구하지 않으므로 방문 처리 표시를 통해 인접한 칸을 더하는 것을 방지한다.

그리고 백트래킹을 통해 완전탐색을 해야하므로 한 번 확인하고 나면 방문처리를 원래대로 돌려주어야 하는데

나는 스택으로 몇 개의 인접한 칸을 방문 처리 표시했는지 기억해두고 다시 되돌려야할 경우 기억했던 개수만큼

다시 스택에서 꺼내 방문처리를 되돌려주었다.

 

난 이렇게 풀긴 했는데 더 효율적인 방법이 존재할 것 같다. 다른 사람의 풀이도 참고해봐야겠다.

#include <iostream>
#include <queue>
#include <vector>
#include <stack>
#include <string>
#include <cstring>
#include <set>
#include <unordered_set>
#include <map> 
#include <algorithm>
#include <cmath>
#define CUNLINK ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ENDL cout << endl
#define ll long long
#define INF 987654321
#define Mod 10007
#define endl '\n'
#define pil pair<int,int>

using namespace std;

int N, M, K, total;
int answer = -INF;
int board[11][11];
bool visited[11][11];

const int dy[] = { 1,-1,0,0 };
const int dx[] = { 0,0,1,-1 };
stack<pair<int, int>> pos, stk;

int Remove(int y, int x) {
	int Cnt = 0;
	for (int i = 0; i < 4; i++) {
		int ny = y + dy[i];
		int nx = x + dx[i];

		if (ny < 1 || ny > N || nx < 1 || nx > M) continue;
		if (visited[ny][nx]) continue;
		visited[ny][nx] = true;
		stk.push({ ny, nx });
		Cnt++;
	}
	return Cnt;
}

void Reverse(int p) {
	for (int i = 0; i < p; i++) {
		pair<int, int> prev = stk.top();
		stk.pop();
		visited[prev.first][prev.second] = false;
	}
}

void func(int depth, int y, int x, int total) {
	if (depth == K) {
		answer = max(answer, total);
		return;
	}

	for (int i = y; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			if (!visited[i][j]) {
				visited[i][j] = true;
				int c = Remove(i, j);

				func(depth + 1, i, j, total + board[i][j]);

				Reverse(c);
				visited[i][j] = false;
			}
		}
	}
}

int main() {
	cin >> N >> M >> K;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cin >> board[i][j];
		}
	}
	
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			visited[i][j] = true;

			int c = Remove(i, j);
			func(1, i, j, board[i][j]);
			Reverse(c);

			visited[i][j] = false;
		}
	}
	cout << answer << endl;

	return 0;
}