[BOJ] 18430 무기공학 - Java

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

18430번: 무기 공학

---

1. 문제 요약

NxM크기의 map에서 부메랑은 항상 3칸을 차지하는 아래의 4개의 모양만 가능하다.

부메랑의 강도는 부메랑 3칸에 해당하는 map 값의 합이며, 부메랑의 중심이 되는 칸은 map 값의 2배가 된다.

즉, 이 녀석의 강도는 5 + 2*2 + 9 인 셈이다.

강도 합의 최댓값을 출력하면 된다.

[제약조건]

- map의 크기가 부메랑이 있을 수 없는 크기라면 0을 출력한다.

2. 풀이

백트래킹 문제이다.

가능한 모든 경우를 탐색하고 그 중에서 최댓값을 갱신해야 한다.

 

1. dfs를 돌 때마다 강도 합의 최댓값을 갱신해주었다. 

     - 각 경우마다 dfs가 끝나는 지점이 다 다르기 때문이다.(dfs가 언제 끝날지 모르기 때문)

2. => 방향으로 쭉 x값을 +1해주다가 x>=M 이 될 경우 y값을 늘려주고 x값은 0으로 초기화해줬다.

3. 이 때 y>=N라면, (y의 범위를 벗어난다면) return하여 가지치기를 해주었다.

4. 이미 y, x 좌표에 부메랑이 놓여져 있다면, 다음좌표(=>)로 dfs를 돈다.

5. 아직 y, x 좌표에 부메랑이 놓여져 있지 않다면, 해당 좌표를 부메랑의 중심으로 4가지 타입의 부메랑을 전부 놓아본다.

    - 놓을 수 있다면 누적합에 현재 부메랑 강도 합을 더해주고, 다음좌표(=>)로 dfs를 돈다.

    - 놓을 수 없다면, (4가지 타입을 다 봤는데도 놓을 수 없어서 for문이 끝났다면)

      누적합 그대로 다음좌표(=>)로 dfs를 돈다.

 

맨 마지막 조건에서 오래걸렸다.

 

3. 코드

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

public class BOJ_18430_무기공학 {

	static int N, M, ans;
	static int[][] map;
	static boolean[][] visited;
	
	static int[] dy1= {-1,-1, 0, 0};
	static int[] dx1= { 0, 0,-1, 1};
	static int[] dy2= { 0, 0, 1, 1};
	static int[] dx2= { 1,-1, 0, 0};
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		map = new int[N][M];
		visited = 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());
			}
		} // 입력 끝
		
		if(N<2 || M<2) {
			System.out.println(0);
			return;
		}
		
		dfs(0,0,0);
		System.out.println(ans);
	}
	
	static void dfs(int y, int x, int sum) {
		ans = Math.max(ans, sum);
		if (x>=M) {
			y++;
			x=0;
		}
		if (y>=N) return;
		
		if (visited[y][x]) {
			dfs(y,x+1,sum);
		} else {

			for (int type=0; type<4; type++) {
				int ny1 = y+dy1[type];
				int nx1 = x+dx1[type];
				int ny2 = y+dy2[type];
				int nx2 = x+dx2[type];
				if (ny1<0 || ny1>=N || nx1<0 || nx1>=M || visited[ny1][nx1]) continue;
				if (ny2<0 || ny2>=N || nx2<0 || nx2>=M || visited[ny2][nx2]) continue;
				
				visited[ny1][nx1] = true;
				visited[ny2][nx2] = true;
				visited[y][x] = true;
				
				int power = map[ny1][nx1] + map[ny2][nx2] + map[y][x]*2;
				dfs( y, x+1, sum+power);
				
				visited[ny1][nx1] = false;
				visited[ny2][nx2] = false;
				visited[y][x] = false;
			}
			dfs( y, x+1, sum);
		}
	}
}