백준 18430 무기 공학 (Java)

1. 문제 링크

18430번: 무기 공학

 

2. 문제 및 입출력예제

 

3. 문제 풀이

1. DFS 탐색을 통해 만들 수 있는 모든 부메랑의 경우를 찾는다.

2. 방문하지 않은 곳에서 만들 수 있는 4가지 부메랑을 만들어본다.

    2-1. 각 부메랑의 조건을 통과하면 방문처리 후 dfs를 진행한다.

    2-2. DFS가 끝나고 돌아오면 방문처리를 다시 원래대로 돌려둔다. (다른 경우에 영향 끼치지 않도록)

 

4. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	static int N, M, map[][], result;
	static boolean[][] visit;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] split = br.readLine().split(" ");
		N = Integer.parseInt(split[0]);
		M = Integer.parseInt(split[1]);
		map = new int[N][M];
		visit = new boolean[N][M];
		result = 0;
		for(int i=0;i<N;i++) {
			split = br.readLine().split(" ");
			for(int j=0;j<M;j++) {
				map[i][j] = Integer.parseInt(split[j]);
			}
		}
		dfs(0, 0);
		System.out.println(result);
	}
	private static void dfs(int cnt, int sum) {
		int i = cnt/M;
		int j = cnt%M;
		if(cnt == N*M) {
			result = Math.max(sum, result);
			return;
		}
		if(!visit[i][j]) {
      visit[i][j] = true;
			//아래, 왼
			if(i+1 < N && j-1 >= 0 && !visit[i+1][j] && !visit[i][j-1]) {
				visit[i+1][j] = true;
				visit[i][j-1] = true;
				dfs(cnt+1, sum+map[i][j]*2 + map[i+1][j] + map[i][j-1]);
				visit[i+1][j] = false;
				visit[i][j-1] = false;
			}
			//위, 왼
			if(i-1 >= 0 && j-1 >= 0 && !visit[i-1][j] && !visit[i][j-1]) {
				visit[i-1][j] = true;
				visit[i][j-1] = true;
				dfs(cnt+1, sum+map[i][j]*2 + map[i-1][j] + map[i][j-1]);
				visit[i-1][j] = false;
				visit[i][j-1] = false;
			}
			//위, 오
			if(i-1 >= 0 && j+1 < M && !visit[i-1][j] && !visit[i][j+1]) {
				visit[i-1][j] = true;
				visit[i][j+1] = true;
				dfs(cnt+1, sum+map[i][j]*2 + map[i-1][j] + map[i][j+1]);
				visit[i-1][j] = false;
				visit[i][j+1] = false;
			}
			//아래, 오
			if(i+1 < N && j+1 < M && !visit[i+1][j] && !visit[i][j+1]) {
				visit[i+1][j] = true;
				visit[i][j+1] = true;
				dfs(cnt+1, sum+map[i][j]*2 + map[i+1][j] + map[i][j+1]);
				visit[i+1][j] = false;
				visit[i][j+1] = false;
			}
      		visit[i][j] = false;
		}
		dfs(cnt+1, sum); //부메랑 안 만들고 넘어가는 경우
	}
}