[BOJ 백준] 18430번 - 무기공학

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

18430번: 무기 공학

전형적인 백트래킹으로 푸는 문제였다.

 

우선, 부메랑은 다음과 같이 4가지 모양을 가질 수 있고, 이를 최대한 많이 사용하여 최대 강도를 만들어 내야 한다.

 

부메랑의 모양

 

 

문제 해결 방법

1. 예를들어 첫번째 부메랑을 만들기 위해서는가운데(y, x)를 기준으로
   • (y,x-1) 과 (y+1, x)가 범위 내에 있어야 하고
   • (y,x-1)과 (y+1, x)가 사용된 적이 없어야 한다.
   • 나머지 부메랑들도 마찬가지이다.
2. 부메랑이 만들어지면 오른쪽으로 한 칸 옮겨가서 다른 부메랑을 더 만든다.
   • 3개의 지점을 방문체크 한다.
   • 문제의 조건에 맞게 부메랑의 강도를 구한다.
   • 오른쪽으로 한칸 움직이고, 새로 구한 부메랑의 강도를 매개변수로 넣어 재귀호출을 한다.(백트래킹)
3. 4개의 부메랑 모양 전부 확인한다.
4. (x == m) 이라면 오른쪽 끝까지 간 것이므로, 한 줄 밑으로 내려가고 맨 왼쪽부터 시작한다
5. (y == n) 이라면 가장 아래쪽까지 다 확인한 것이므로, 최종 부메랑 강도의 합계 중 최댓값을 구한 뒤 리턴한다.

 

 

 

소스코드

#include <bits/stdc++.h>
#define MAX 5
#define endl "\n"
using namespace std;
int n, m;
int Map[MAX][MAX];
bool visited[MAX][MAX];

int rightUp(int y, int x) {
    return Map[y][x - 1] + Map[y + 1][x] + 2 * Map[y][x];
}
int rightDown(int y, int x) {
    return Map[y - 1][x] + Map[y][x - 1] + 2 * Map[y][x];
}
int leftUp(int y, int x) {
    return Map[y][x + 1] + Map[y + 1][x] + 2 * Map[y][x];
}
int leftDown(int y, int x) {
    return Map[y - 1][x] + Map[y][x + 1] + 2 * Map[y][x];
}
int ans = 0;

void dfs(int y, int x, int sum) {
    if (x == m) {
        x = 0;
        y++;
    }
    if (y == n) {
        ans = max(ans, sum);
        return;
    }
    if (!visited[y][x]) {
        if (y + 1 < n && x - 1 >= 0 && !visited[y + 1][x] && !visited[y][x - 1]) {
            visited[y][x] = true;
            visited[y][x - 1] = true;
            visited[y + 1][x] = true;
            int nsum = sum + rightUp(y, x);
            dfs(y, x + 1, nsum);
            visited[y][x] = false;
            visited[y][x - 1] = false;
            visited[y + 1][x] = false;
        }
        if (y - 1 >= 0 && x - 1 >= 0 && !visited[y - 1][x] && !visited[y][x - 1]) {
            visited[y][x] = true;
            visited[y - 1][x] = true;
            visited[y][x - 1] = true;
            int nsum = sum + rightDown(y, x);
            dfs(y, x + 1, nsum);
            visited[y][x] = false;
            visited[y - 1][x] = false;
            visited[y][x - 1] = false;
        }
        if (y + 1 < n && x + 1 < m && !visited[y + 1][x] && !visited[y][x + 1]) {
            visited[y][x] = true;
            visited[y][x + 1] = true;
            visited[y + 1][x] = true;
            int nsum = sum + leftUp(y, x);
            dfs(y, x + 1, nsum);
            visited[y][x] = false;
            visited[y][x + 1] = false;
            visited[y + 1][x] = false;
        }
        if (y - 1 >= 0 && x + 1 < m && !visited[y - 1][x] && !visited[y][x + 1]) {
            visited[y][x] = true;
            visited[y - 1][x] = true;
            visited[y][x + 1] = true;
            int nsum = sum + leftDown(y, x);
            dfs(y, x + 1, nsum);
            visited[y][x] = false;
            visited[y - 1][x] = false;
            visited[y][x + 1] = false;
        }
    }
    dfs(y, x + 1, sum);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
  //  freopen("input.txt", "r", stdin);
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> Map[i][j];
        }
    }
    dfs(0, 0, 0);
    cout << ans;
    return 0;
}