[Algorithm]Baekjoon 18430번 :: 무기 공학

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

 

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_set>
 
using namespace std;
 
 
 
int n, m;
int answer = 0;
bool visited[7][7] = { false };
int wood[7][7];
 
 
bool IsValidLocation(int y, int x)
{
    if (y < 0 || y == n) return false;
    if (x < 0 || x == m) return false;
    if (visited[y][x]) return false;
 
    return true;
}
 
 
int dirs[4][2][2] =
{
    {
        {0,-1}, {1,0}
    },
    {
        {0,-1}, {-1,0}
    },
    {
        {-1,0}, {0,1}
    },
    {
        {1,0}, {0,1}
    }
};
 
 
void DFS(int cy, int cx, int sumStrength)
{
    if (cy == n)
    {
        cy = 0;
        ++cx;
    }
 
    if (cx == m) return;
 
    if (!visited[cy][cx])
    {
        visited[cy][cx] = true;
        int curStrength = wood[cy][cx] * 2;
 
        for (int i = 0; i < 4; ++i) // 부메랑 만들기 시도해보기.
        {
            int y1 = cy + dirs[i][0][0];
            int x1 = cx + dirs[i][0][1];
            int y2 = cy + dirs[i][1][0];
            int x2 = cx + dirs[i][1][1];
 
            if (IsValidLocation(y1, x1) && IsValidLocation(y2, x2)) // 부메랑 만들기.
            {
                curStrength += wood[y1][x1] + wood[y2][x2];
                answer = max(answer, sumStrength + curStrength);
 
                visited[y1][x1] = true;
                visited[y2][x2] = true;
                 
                DFS(cy+1, cx, sumStrength + curStrength);
 
                visited[y1][x1] = false;
                visited[y2][x2] = false;
                curStrength -= wood[y1][x1] + wood[y2][x2];
            }
        }
 
        visited[cy][cx] = false;
    }
 
 
    // 부메랑 안만들고 넘어가기.
    DFS(cy+1, cx, sumStrength);
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n >> m;
 
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            cin >> wood[i][j];
        }
    }
 
    DFS(0, 0, 0);
 
    cout << answer;
}
 
 

 

내가 완전탐색에 약했다는 걸 알 수 있었던 문제... 사실은 알고있긴 했었지만..

 

부메랑을 만들고 다음 탐색지점을 찾는거를 다시 2중포문으로 처음부터 돌렸더니 통과는했다만 1000ms대가 나왔다.

다른사람 풀이보고나서야 이해를 해서 적용시켰다.

 

실제 코테때는 이정도의 문제는 굉장히 빨리 풀어야하는데;; 큰일날뻔했다.