[백준] 18430번: 무기 공학 | C++

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

18430번: 무기 공학

 

틀린 이유

안 쓰려다가 날 너무 괴롭혀서 쓴다...

 

1. 처음 접근 때는 백트랙킹 메서드 안에 for 문을 두 개 돌렸었다. 인수로 x, y 좌표를 입력 받고 인수에서 시작하는 for 문 두 개.... (이것이 근본적으로 틀린 접근이었다.) 아무튼 처음 틀린 이유는 (1) for 문을 돌릴 때 p,q,x,y 변수를 아예 틀리게 써서 틀렸다. 

→ 오타를 인지 못했다는 뜻

2. 오타를 고치고 돌렸는데 틀렸다. 알고보니 인수로 받은 좌표부터 시작하니 y좌표가 M-1일 경우 앞 좌표를 탐색하지 않고 넘어가는 것을 인지했다.

3. 눈물을 머금고 0부터 시작하는 for 문 두 개 돌리니 답은 맞는데, 당연히 시간초과가 났다.

이런 방식...

 

4. 두 시간 고민하닥 결국 정답 찾아보고 내 접근이 틀렸다는 것을 인지했다.

 

 

지금 생각하니 쉬운 방법이 있는데 왜 for 문을 두 개 돌렸을까? 아마 백트랙킹에 익숙하지 않기 때문이겠지. 완전 탐색에 약한 것은 완전 탐색을 많이 풀어보지 않은 이유라고 생각한다. 그리디처럼 아이디어를 도출해내야 하는 알고리즘이 아니기 때문에 문제 많이 풀어 봐야겠다.

 

 

정답코드

완전탐색에 익숙하다면 어렵지 않을 것 같다^^!!!

평범한 2차원 완전탐색 알고리즘이다. 그런데 나는 바보인

#include<iostream>
#include<algorithm>
#include<vector>
#define MAX 6
using namespace std;
int N,M;
int a[MAX][MAX];
bool visit[MAX][MAX];
int dx[4][2]={{0,1},{-1,0},{-1,0},{1,0}};
int dy[4][2]={{1,0},{0,1},{0,-1},{0,-1}};
int ans;
void bt(int p,int q,int power){
    if(q==M){
        q=0;
        p++;
    }
    if(p==N) {
        ans=max(ans,power);
        return;
    }
    
    if(!visit[p][q]){
        for(int i=0;i<4;i++){ // ...(1)
            int nx1=p+dx[i][0];
            int ny1=q+dy[i][0];
            int nx2=p+dx[i][1];
            int ny2=q+dy[i][1];
            if(0<=nx1&&nx1<N&&0<=nx2&&nx2<N&&\
                0<=ny1&&ny1<M&&0<=ny2&&ny2<M&&\
                !visit[nx1][ny1] && !visit[nx2][ny2])
            {
                visit[p][q]=1;
                visit[nx1][ny1]=1;
                visit[nx2][ny2]=1;
                int tmp=a[p][q]*2+a[nx1][ny1]+a[nx2][ny2];
                bt(p,q+1,power+tmp);
                visit[p][q]=0;
                visit[nx1][ny1]=0;
                visit[nx2][ny2]=0;
            }
        }
    }   
    bt(p,q+1,power); // 부메랑을 만들지 않고 넘기기
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>N>>M;
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            cin>>a[i][j];
        }
    }
    bt(0,0,0);
    cout<<ans;
}