백준 18430 - 무기 공학

문제 설명

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

256 MB

2557

1220

895

46.932%

문제

공학자 길동이는 외부의 침략으로부터 마을을 지킬 수 있는 부메랑 무기를 개발하는 공학자다. 길동이는 부메랑 제작을 위한 고급 나무 재료를 구했다. 이 나무 재료는 NxM크기의 직사각형 형태이며 나무 재료의 부위마다 그 강도가 조금씩 다르다.

예를 들어 나무 재료의 크기가 2x3일 때는 다음과 같이 총 6칸으로 구성된다.

길동이는 이처럼 넓은 사각형 형태의 나무 재료를 잘라서 여러 개의 부메랑을 만들고자 한다. 그리고 부메랑은 항상 3칸을 차지하는 ‘ㄱ’모양으로 만들어야 한다. 따라서 부메랑의 가능한 모양은 다음과 같이 총 4가지다.

이때 부메랑의 중심이 되는 칸은 강도의 영향을 2배로 받는다. 위 그림에서 노란색으로 칠한 부분이 ‘중심이 되는 칸’이다. 예를 들어 앞선 예시에서는 다음과 같이 2개의 부메랑을 만들 수 있으며, 이때 만들어지는 부메랑들의 강도의 합은 46으로 이보다 강도의 합이 높아지는 경우는 없다.

또한 나무 재료의 특정 위치는 아예 사용하지 않아도 괜찮다. 예를 들어 앞선 예시에서 다음과 같이 1개의 부메랑만을 만들어도 괜찮다. 다만, 이렇게 만들게 되면 부메랑들의 강도의 합이 18이 되기 때문에 비효율적이다.

나무 재료의 형태와 각 칸의 강도가 주어졌을 때, 길동이가 만들 수 있는 부메랑들의 강도 합의 최댓값을 출력하는 프로그램을 작성하시오. 

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

 

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, 주어진 2차원 배열에서 3칸씩 뜯어 부메랑을 만드는데 부메랑의 숫자의 합이 가장 크게 만드는 경우를 찾는 것이다.

이때, 부메랑의 중심은 2배로 계산한다.

 

아무래도 숫자가 가장 큰 칸이 중심이 되어 부메랑을 제작하는 것이 가장 이득이되는 경우라고 생각할 수 있다.

하지만, 이는 항상 최적해를 보장하지는 않는다.

예를 들어 보자.

가장 큰 숫자인 96을 중심으로 부메랑을 만든다면 위와 같은 상황이 된다.

이렇게 구성한 결과는 585이다.

물론 방향을 돌려 더 크게 만들 수도 있다.

하지만, 정답은 다음과 같이 부메랑을 만들 때이다.

이 경우의 답은 632이 된다.

 

즉, 그리디로는 문제를 풀 수 없다.

따라서 모든 경우를 계산해봐야 한다.

이는 N의 크기로 힌트를 얻을 수 있다.

N, M의 크기가 5이하로 매우 작기 때문에 $O(N^2)$의 연산은 거뜬히 할 수 있다.

 

모든 경우를 계산하는 작업은 다음과 같다.

1. 임의의 칸을 중심으로 부메랑을 만들 수 있는지 판단한다.
   • 만들 수 있다면 포함되는 칸을 표시하고 다음 부메랑을 만든다.
   • 만들 수 없다면 다음 칸으로 이동한다.
2. 이전의 만든 부메랑과 겹치지 않는 다른 부메랑을 만든다.
3. 모든 칸을 돌았다면 다시 돌아와 방향을 돌리며 다른 경우를 탐색한다.

즉, 백트래킹으로 문제를 풀 수 있다.

 

부메랑을 만드는 과정은 변위를 통해 간단하게 할 수 있다.

vector<vector<int>> dy = { {0, 1}, {-1, 0}, {-1, 0}, {0, 1} };
vector<vector<int>> dx = { {-1, 0}, {0, -1}, {0, 1}, {1, 0} };

...
for (int i = 0; i < 4; i++)
{
  int y1 = y + dy[i][0];
  int x1 = x + dx[i][0];
  
  int y2 = y + dy[i][1];
  int x2 = x + dx[i][1];

  if (y1 < 0 || y1 >= N || x1 < 0 || x1 >= M) continue;
  if (y2 < 0 || y2 >= N || x2 < 0 || x2 >= M) continue;

  if (visited[y1][x1] || visited[y2][x2]) continue;
  
  ...
}

위는 겹치는 부메랑이 있는지 판단하는 과정이다.

겹치는 부메랑이 없다면 부메랑을 만들고 다른 칸을 탐색해 보면 된다.

이때, 탐색을 왼쪽에서 오른쪽으로, 위쪽에서 아래쪽으로 진행하기 때문에 현재 칸의 왼쪽, 위쪽으로는 진행할 필요가 없다.

이미 탐색한 곳이기 때문이다.

int currentStrenth = Boomerang[y][x] * 2 + Boomerang[y1][x1] + Boomerang[y2][x2];
visited[y][x] = true;
visited[y1][x1] = true;
visited[y2][x2] = true;

int temp = 0;
int c = x + 1;
for (int r = y; r < N; r++)
{
    for (; c < M; c++)
    {
        if (visited[r][c]) continue;
        temp = max(temp, DFS(Boomerang, visited, r, c));
    }
    c = 0;
}

탐색을 마치면 최대값이 temp에 있을 것이다.

그럼 현재 부메랑의 강도를 더해 return 하면 된다.

또한, 현재 부메랑을 만들었다는 표시를 해제해야 한다.

visited[y][x] = false;
visited[y1][x1] = false;
visited[y2][x2] = false;

result = max(result, currentStrenth + temp);

---

 

 

 

 

 

전체 코드

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <climits>
#include <queue>
#include <map>
#include <set>

using namespace std;

int N, M;

vector<vector<int>> dy = { {0, 1}, {-1, 0}, {-1, 0}, {0, 1} };
vector<vector<int>> dx = { {-1, 0}, {0, -1}, {0, 1}, {1, 0} };

int DFS(vector<vector<int>>& Boomerang, vector<vector<bool>>& visited, int y, int x)
{
    int result = 0;

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

        int y2 = y + dy[i][1];
        int x2 = x + dx[i][1];

        if (y1 < 0 || y1 >= N || x1 < 0 || x1 >= M) continue;
        if (y2 < 0 || y2 >= N || x2 < 0 || x2 >= M) continue;

        if (visited[y1][x1] || visited[y2][x2]) continue;

        int currentStrenth = Boomerang[y][x] * 2 + Boomerang[y1][x1] + Boomerang[y2][x2];
        visited[y][x] = true;
        visited[y1][x1] = true;
        visited[y2][x2] = true;

        int temp = 0;
        int c = x + 1;
        for (int r = y; r < N; r++)
        {
            for (; c < M; c++)
            {
                if (visited[r][c]) continue;
                temp = max(temp, DFS(Boomerang, visited, r, c));
            }
            c = 0;
        }

        visited[y][x] = false;
        visited[y1][x1] = false;
        visited[y2][x2] = false;

        result = max(result, currentStrenth + temp);
    }

    return result;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M;

    vector<vector<int>> Boomerang(N, vector<int>(M, 0));
    vector<vector<bool>> visited(N, vector<bool>(M, false));

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

    int answer = 0;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            answer = max(answer, DFS(Boomerang, visited, i, j));
        }
    }

    cout << answer;

	return 0;
}

---