소프티어 - 함께하는 효도(C++)

https://softeer.ai/practice/7727

Softeer - 현대자동차그룹 SW인재확보플랫폼

 

소프티어에서는 처음 문제를 풀어보는데 나쁘지 않은 문제인 것 같다.

dfs 백트래킹 문제에 더불어 재귀적인 요소를 포함하고 있었다. 내 풀이가 정해인진 모르겠는데 일단은 맞았다.

 

아이디어는 이러하다.

문제를 파악했을태니 이 각 친구들은 각자 나무에서 열매를 따는데, 만약 A가 이미 땄다면 B는 거기서 열매를 딸 수 없다. 이 조건 때문에 문제가 까다로워진다.

 

그래서 난 visited배열을 3차원으로 설정하고, A가 열매를 다 따면 B가 열매를 따며 조절하는데 각자 방문 배열이 존재하면서 다음으로 갔을 때 다른 차원의 배열이 만약 방문표시 되어있다면 열매를 따지 않도록 조절했다.

 

이 때 차원을 관리하는 파라미터를 dfs에 추가하여 관리했다. 조금 까다로웠지만 침착하게 해봤다.

 

그리고 중요한 조건이 있는데 모든 친구들은 적어도 하나의 열매는 딸 수가 있다. 왜냐하면 시작점에서는 모두 딸 수 있기 때문이다. 그러므로 시작하기 전에 모든 친구들의 시작점은 각 차원배열에서 방문표시를 해놔야한다.

 

#include <iostream>
#include <vector>
using namespace std;

int N, M;
bool visited[21][21][4] = { false, };
int tree[21][21];

vector<pair<int, int>> startset;

int answer = 0;
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
void dfs(int x, int y, int cnt, int value, int dim) {
	if (cnt == 3) {
		if (dim == 1) {
			answer = max(answer, value);
            return;
		}
		else {
            int nx = startset[dim - 2].first - 1;
            int ny = startset[dim - 2].second - 1;
			dfs(nx, ny, 0, value + tree[nx][ny], dim - 1);
            return;
		}
	}

	for (int i = 0; i < 4; i++) {
		int nextx = x + dx[i];
		int nexty = y + dy[i];

		if (nextx < N && nextx > -1 && nexty < N && nexty > -1 && visited[nextx][nexty][dim] == false) {
			visited[nextx][nexty][dim] = true;
			int nextValue = value;
			if (dim == 3) nextValue += tree[nextx][nexty];
			else if (dim == 2) {
				if (visited[nextx][nexty][3] == false) nextValue += tree[nextx][nexty];
			}
			else if (dim == 1) {
				if (visited[nextx][nexty][2] == false && visited[nextx][nexty][3] == false) nextValue += tree[nextx][nexty];
			}

			dfs(nextx, nexty, cnt + 1, nextValue, dim);
			visited[nextx][nexty][dim] = false;
		}
	}
}

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

	cin >> N >> M;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> tree[i][j];
		}
	}

	for (int j = 0; j < M; j++) {
		int a, b;
		cin >> a >> b;
		startset.push_back({ a,b });
	}

    for(int i = 0; i < startset.size(); i++){
        int x = startset[i].first - 1;
        int y = startset[i].second - 1;
        visited[x][y][i + 1] = true;
    }
    
    int x = startset[startset.size() - 1].first - 1;
    int y = startset[startset.size() - 1].second - 1;
	dfs(x, y, 0, tree[x][y], M);

	cout << answer << endl;
}