[백준,c++] 18430번 - 무기 공학

문제

18430번: 무기 공학

코드

#include <iostream>
#include <vector>

using namespace std;

int N, M , ans;
int map[6][6];
bool visited[6][6];
vector<pair<int,int>> coor[4] = { {{-1, 0 }, {0, 1}}, {{-1,0}, {0, -1}}, {{0, -1}, {1, 0}}, {{0, 1}, {1,0}} };

void backtracking(int x, int y, int sum){
    ans = max(ans, sum);
    
    if(y==M){
        y = 0;
        x++;
    }
    
    if(x==N) return;

    if(!visited[x][y]){
        for(int c = 0; c<4; c++){   // 부메랑 만들고 넘어가기
            int nx1 = x + coor[c][0].first;
            int ny1 = y + coor[c][0].second;
            int nx2 = x + coor[c][1].first;
            int ny2 = y + coor[c][1].second;
            
            if(nx1>=0 && nx2>=0 && nx1<N && nx2<N && ny1>=0 && ny2>=0 && ny1<M && ny2<M){
                if(visited[nx1][ny1] || visited[nx2][ny2]) continue;
                visited[nx1][ny1] = 1;
                visited[nx2][ny2] = 1;
                visited[x][y] = 1;
                
                backtracking(x, y+1, sum + (map[x][y]*2) + map[nx1][ny1] + map[nx2][ny2]);
                
                visited[x][y] = 0;
                visited[nx1][ny1] = 0;
                visited[nx2][ny2] = 0;
            }
        }
    }
    backtracking(x, y+1, sum);  // 부메랑 만들지 않고 넘어가기
}


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
        
    cin>>N>>M;
    
    for(int i=0; i<N; i++){
        for(int k=0; k<M; k++){
            cin>>map[i][k];
        }
    }
    
    backtracking(0, 0, 0);
    cout<<ans;
}

풀이

다음과 같은 배열에서 아래와 같이 ㄱ모양으로 만들 수 있는 아래의 네 가지 부메랑을 만들었을 때의 숫자의 최대 합을 찾는 문제입니다.

해당 칸에 노란색으로 칠해진 부분은 중심칸이라고 불리며, 해당 칸은 점수가 두배로 더해지게 됩니다.

[백준,c++] 14712번 - 넴모넴모 (Easy)

이전에 위 문제에서 사용했던 방식처럼 배열의 순서는 (0,0) , (0,1), (0,2),..., (0,N), (1, 0)... (N , M) 방식으로 선택하게 구현하였고, 부메랑을 만드는 방법은 bfs와 dfs 방향 탐색 문제에서 사용했던 방법과 동일하게 구현했습니다.