[SOFTEER] 함께하는 효도 (DFS 탐색 시 각 노드의 데이터 설계 주의)

문제출처

• 함께하는 효도

문제접근

• 각 친구들이 3초 동안 움직일 수 있는 모든 경우의 수를 DFS 를 통해 찾는다.
  • 한 사람이 3초 동안 위치할 수 있는 좌표 정보를 하나의 원소로 담는다.
• 각 친구들의 모든 움직임에 대한 경우의 수를 가지고 모든 조합을 찾는다.
• 수확량의 최댓값을 계산한다.

구현

#include <iostream>
#include <memory.h>
#include <vector>
#include <queue>
#include <algorithm>

#define MAX_TIME 4
#define MAX_N 21
#define MAX_FRIEND 3
using namespace std;

typedef struct _move_info {
    int xpos[MAX_TIME];
    int ypos[MAX_TIME];
} MOVE_INFO_t;

int n, m;
int board[MAX_N][MAX_N];
int calBoard[MAX_N][MAX_N];
int visited[MAX_N][MAX_N];
vector<MOVE_INFO_t> table[3];
MOVE_INFO_t tmp;
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };

int getAmount()
{
    int ret = 0;
    for(int r=1; r<=n; r++){
        for(int c=1; c<=n; c++){
            if(calBoard[r][c] >= 1) ret += board[r][c];
        }
    }
    return ret;
}

int dfs(int friendIdx)
{
    if(friendIdx == m) {
        return getAmount();
    }

    int ret = 0;
    for(int i=0; i<table[friendIdx].size(); i++){
        for(int time=0; time<4; time++){
            int xpos = table[friendIdx][i].xpos[time];
            int ypos = table[friendIdx][i].ypos[time];
            calBoard[xpos][ypos]++;
        }
        ret = max(ret, dfs(friendIdx+1));
        for(int time=0; time<4; time++){
            int xpos = table[friendIdx][i].xpos[time];
            int ypos = table[friendIdx][i].ypos[time];
            calBoard[xpos][ypos]--;
        }
    }
    return ret;
}

void updateAllCase(int friendIdx, int xpos, int ypos, int time)
{
    if (time > 3) {
        table[friendIdx].push_back(tmp);
        return;
    }

    for (int dir = 0; dir < 4; dir++) {
        int nx = xpos + dx[dir];
        int ny = ypos + dy[dir];
        if (nx <= 0 || nx > n || ny <= 0 || ny > n) continue;
        if (visited[nx][ny]) continue;
        visited[nx][ny] = true;
        tmp.xpos[time] = nx;
        tmp.ypos[time] = ny;
        updateAllCase(friendIdx, nx, ny, time + 1);
        visited[nx][ny] = false;
    }
}

void updateFriendMoveInfo(vector<pair<int, int>>& friendPos)
{
    for(int i=0; i<m; i++){
        memset(visited, false, sizeof(visited));
        visited[friendPos[i].first][friendPos[i].second] = true;
        tmp.xpos[0] = friendPos[i].first;
        tmp.ypos[0] = friendPos[i].second;
        updateAllCase(i, friendPos[i].first, friendPos[i].second, 1);
    }
}

int main(int argc, char** argv)
{
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    cin >> n >> m;
    for (int r = 1; r <= n; r++) {
        for (int c = 1; c <= n; c++) {
            cin >> board[r][c];
        }
    }

    vector<pair<int, int>> friendPos;
    int x, y;
    for (int i = 0; i < m; i++) {
        cin >> x >> y;
        friendPos.push_back(make_pair(x, y));
    }
    updateFriendMoveInfo(friendPos);
    memset(calBoard, 0, sizeof(calBoard));
    cout << dfs(0) << endl;
    return 0;
}