[Java] 백준 18430번 : 무기 공학*

1. 문제

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

18430번: 무기 공학

 

 

 

2. 풀이과정

방문체크를 3개씩 하는 DFS 문제이다.

처음에 N, M이 5이하라서 방문체크를 비트마스킹으로 풀었는데, boolean으로 풀었을 때가 1.5배나 빨랐다.

 

비트마스킹은 배열이 아닌 int로 풀어서 2차원 배열 <=> 1차원 배열 전환하는 연산이 많아서 느렸던 것 같다.

+) 벽세우기를 한 후, 1.5배 더 빨라졌다.

 

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

public class Main {
	static int N, M, map[][], result;
	static int dx[][] = {{0, 1}, {-1, 0}, {-1, 0}, {0, 1}}, dy[][] = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};
	
	public static void combination(int now, boolean[][] visited, int strength) {
		if(now >= N*M) {
			result = Math.max(result, strength);
			return;
		}
		
		int x = now/M+1;
		int y = now%M+1;
		if(visited[x][y]) {combination(now+1, visited, strength);}
		else {
			for(int i=0; i<4; i++) {
				int nx = x + dx[i][0];
				int ny = y + dy[i][0];
				int mx = x + dx[i][1];
				int my = y + dy[i][1];
				//범위 밖이면 continue
				if(map[nx][ny]==0 || map[mx][my]==0) {continue;}
				if(visited[nx][ny] || visited[mx][my]) {continue;}
				visited[x][y] = visited[nx][ny] = visited[mx][my] = true;
				combination(now+1, visited, strength + map[x][y]*2 + map[nx][ny] + map[mx][my]);
				visited[x][y] = visited[nx][ny] = visited[mx][my] = false;
			}
			combination(now+1, visited, strength);
		}
		
	}
	
	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+2][M+2];
		for(int i=1; i<=N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=1; j<=M; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		//
		combination(0, new boolean[N+1][M+1], 0);
		System.out.println(result);
	}

}

 

결과