[BOJ] 18430. 무기 공학 - Java

📝 문제

문제 | 백준 18430. 무기 공학

💡 풀이 과정

⛓ 사용한 알고리즘: 완전탐색, 구현

전체 맵의 최대 크기가 25이고, 각 맵의 숫자 또한 100이하로 작기 때문에 문제 조건에 충실하게 구현하여 풀 수 있다. 따라서 특정 좌표에 대해 부메랑을 만들 수 있는지 체크하고, 만들 수 있다면 다른 좌표에 또 다른 부메랑 모양을 만드는 과정을 반복하면 된다. 따라서 종료 조건은 모든 배열을 탐색한 경우이다.

만약 특정 좌표를 부메랑 모양으로 잘랐다면 자른 상태에서 다른 좌표를 잘라낼 수 있는지 추가로 파악해야 하기 때문에 재귀 형식의 함수 dfs 를 선언하여 사용했다.

탐색 종료 조건

모든 좌표를 탐색했는지를 체크하는 방식을 고민하다가 i 좌표와 j 좌표를 하나의 int 형 변수 tmp 로 가지고 다니면서 tmp==N*M 일 때까지 탐색을 진행하는 방식을 사용했다. 모든 좌표를 탐색 완료했다면 무기 강도의 최댓값을 갱신해준다.

if(tmp==N*M) {
	max = Math.max(max, sum);
	return;
}
		
	int ti = tmp/M;
	int tj = tmp%M;

부메랑 모양 유효성 체크

문제에서 나무를 부메랑 모양으로 자를 수 있고 중심 칸은 강도가 2배가 된다고 했기 때문에, 해당 부메랑 모양으로 델타 좌표를 생성해서 사용했다.

static int[][] di = {{0,1}, {0,1}, {-1,0}, {-1,0}};
static int[][] dj = {{-1,0}, {1,0}, {0,-1}, {0,1}};

예를 들어 현재 탐색 대상의 좌표가 색칠한 부분이라고 했을 때, 각 부메랑 모양의 델타 좌표는 위와 같다. 따라서 각 경우에 모든 좌표가 유효한 좌표라면(전체 map 의 범위 안에 있고 아직 방문하지 않은 좌표) 해당 부메랑 모양은 가능한 모양임을 판단할 수 있다.

if(!visit[ti][tj]) {
		
	for(int d=0;d<4;d++) {
		//부메랑 모양 가능한지 체크 
		int i1 = ti+di[d][0];
		int i2 = ti+di[d][1];
		int j1 = tj+dj[d][0];
		int j2 = tj+dj[d][1];
				
		if(isPossible(i1,i2,j1,j2)) {
			visit[ti][tj] = true;
			visit[i1][j1] = true;
			visit[i2][j2] = true;
			dfs(tmp+1, sum+(map[ti][tj]*2)+map[i1][j1]+map[i2][j2]);
			visit[ti][tj] = false;
			visit[i1][j1] = false;
			visit[i2][j2] = false;
		}
	}
}

유효성을 체크하는 함수는 boolean 형 isPossible 함수를 만들어 체크했다. 부메랑 모양으로 자르기 위해서는 세 좌표가 모두 이전에 방문하지 않았고 범위 내에 있어야 하기 때문에 이 조건 중 하나라도 충족하지 못할 경우 false 를 리턴한다.

static boolean isPossible(int i1, int i2, int j1, int j2) {
		if(i1<0 || i2<0 || i1>=N || i2>=N) return false;
		
		if(j1<0 || j2<0 || j1>=M || j2>=M) return false;
		
		if(visit[i1][j1]) return false;
		
		if(visit[i2][j2]) return false;
		
		return true;
}

코드

import java.util.*;
import java.io.*;

public class Main {
	
	static int N,M,max;
	
	static int[][] map;
	static boolean[][] visit;
	
	static int[][] di = {{0,1}, {0,1}, {-1,0}, {-1,0}};
	static int[][] dj = {{-1,0}, {1,0}, {0,-1}, {0,1}};
	
	static boolean isPossible(int i1, int i2, int j1, int j2) {
		if(i1<0 || i2<0 || i1>=N || i2>=N) return false;
		
		if(j1<0 || j2<0 || j1>=M || j2>=M) return false;
		
		if(visit[i1][j1]) return false;
		
		if(visit[i2][j2]) return false;
		
		return true;
	}
	
	static void dfs(int tmp, int sum) {
		if(tmp==N*M) {
			max = Math.max(max, sum);
			return;
		}
		
		int ti = tmp/M;
		int tj = tmp%M;
		
		if(!visit[ti][tj]) {
		
			for(int d=0;d<4;d++) {
				//부메랑 모양 가능한지 체크 
				int i1 = ti+di[d][0];
				int i2 = ti+di[d][1];
				int j1 = tj+dj[d][0];
				int j2 = tj+dj[d][1];
				
				if(isPossible(i1,i2,j1,j2)) {
					visit[ti][tj] = true;
					visit[i1][j1] = true;
					visit[i2][j2] = true;
					dfs(tmp+1, sum+(map[ti][tj]*2)+map[i1][j1]+map[i2][j2]);
					visit[ti][tj] = false;
					visit[i1][j1] = false;
					visit[i2][j2] = false;
				}
			}
		}
		
		dfs(tmp+1, sum);
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		max = Integer.MIN_VALUE;
		
		map = new int[N][M];
		visit = new boolean[N][M];
		
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0;j<M;j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		dfs(0,0);
		System.out.println(max);
	}
}