백준 18430번 무기공학 (C++)

문제 링크 : https://www.acmicpc.net/problem/18430

18430번: 무기 공학

문제 요약

 

 

 

핵심 포인트

 

백 트래킹을 활용해서 풀면 됩니다.

이때 부메랑을 만들 수 있는 4가지 모양을 판별하는 것이 중요합니다.

 

부메랑의 모양은 일반적인 회전 모형처럼 for문을 돌려서 판별할 경우 갔던 경로를 되돌리는 과정의 구현이 번거로울 수 있으므로, for문을 사용하지 않고 각각 별개로 구현하는 것을 권장합니다.

 

 

문제 풀이

 

전체 코드입니다.

#include <iostream>
#include <algorithm>
using namespace std;

int n,m,arr[5][5], temp, ans; // 4 ways
bool ch[5][5];

int first(int y, int x) {return arr[y][x]*2 + arr[y+1][x] + arr[y][x-1];}
int second(int y, int x) {return arr[y][x]*2 + arr[y-1][x] + arr[y][x-1];}
int third(int y, int x) {return arr[y][x]*2 + arr[y-1][x] + arr[y][x+1];}
int fourth(int y, int x) {return arr[y][x]*2 + arr[y][x+1] + arr[y+1][x];}

void input(){
	cin >> n >> m;
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++) cin >> arr[i][j];
	}
}

void backTracking(int y, int x, int sum){
	if(x==m){
		x = 0;
		y++;
	}
	if(y==n){
		ans = max(ans,sum);
		return;
	}
	if(!ch[y][x]){
		if(y+1<n&&x-1>=0&&!ch[y+1][x]&&!ch[y][x-1]){
			ch[y][x] = true;
			ch[y+1][x] = true;
			ch[y][x-1] = true;
			temp = sum + first(y,x);
			backTracking(y,x+1,temp);
			ch[y][x] = false;
			ch[y+1][x] = false;
			ch[y][x-1] = false;
		}
		if(y-1>=0&&x-1>=0&&!ch[y-1][x]&&!ch[y][x-1]){
			ch[y-1][x] = true;
			ch[y][x-1] = true;
			ch[y][x] = true;
			temp = sum + second(y,x);
			backTracking(y,x+1,temp);
			ch[y-1][x] = false;
			ch[y][x-1] = false;
			ch[y][x] = false;
		}
		if(y-1>=0&&x+1<m&&!ch[y-1][x]&&!ch[y][x+1]){
			ch[y-1][x] = true;
			ch[y][x] = true;
			ch[y][x+1] = true;
			temp = sum + third(y,x);
			backTracking(y,x+1,temp);
			ch[y-1][x] = false;
			ch[y][x] = false;
			ch[y][x+1] = false;
		}
		if(y+1<n&&x+1<m&&!ch[y+1][x]&&!ch[y][x+1]){
			ch[y][x] = true;
			ch[y+1][x] = true;
			ch[y][x+1] = true; 
			temp = sum + fourth(y,x);
			backTracking(y,x+1,temp);
			ch[y][x] = false;
			ch[y+1][x] = false;
			ch[y][x+1] = false;
		}
	}
	backTracking(y,x+1,sum);
	return;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	input();
	if(n==1||m==1) cout << 0 << "\n";
	else{
		backTracking(0,0,0);
		cout << ans << "\n";
	}
    return 0;
}

 

맨 위의 first ~ fourth는 문제에서 요구하는 4개의 모양에 대한 각각의 점수합산 함수입니다.

y,x가 블록의 센터(이미지에서 노란색으로 표시된 부분, 점수가 2배인 부분)에 해당됩니다.

 

first ~ fourth의 모양별로 방문이 가능한지 아닌지를 판단한 뒤, 방문이 가능할 경우 점수를 새로 합산하여 다음 경로로 백 트래킹을 계속 진행하면 됩니다.

이때 방문을 종료했을 경우 다시 되돌아올 수 있도록 방문을 해제하는 과정을 잊어서는 안됩니다.

 

만약 방문이 불가능할 경우, 다음 경로로 백 트래킹을 계속 진행하면 됩니다.