[devmoon]백준 18403 - (Java) 무기공학

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

18430번: 무기 공학

1. 유형

백트래킹, 구현

 

2. 시뮬레이션

 

로직

• 2중 반복문으로 범위 탐색
• 부메랑 부분 체크
• 최대값 확인

시뮬레이션을 돌리면

위의 그림처럼 여러가지 경우의 수가 나옵니다. 특히, 노란색 ㄱ모양 부메랑을 만들고,

그 후에 빈칸에 따라 만들수 있는 부메랑을 확인합니다. 즉, 부메랑 한개를 만들때마다 재귀를사용하면 됩니다.

 

이때 범위지정을 잘 해야합니다. 3*3인 경우 아래같은 범위만 탐색하면 됩니다.

 

위의 4개의 칸 마다 총 5가지의 경우의 수가 존재합니다.

ㄱ을 90도 만큼 돌린경우 4개, 그리고 만들지 않는 경우 총 5가지 입니다.

완전탐색을 돌리되 해당 자리에서 무기를 만들지 못하면 백트래킹을 합니다.

 

3. 코드

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

public class Main {
	static int N, M, map[][],answer;

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine());
		N = stoi(st.nextToken());
		M = stoi(st.nextToken());
		map = new int[N][M];
		answer =0;
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(in.readLine());
			for (int j = 0; j < M; j++) {
				map[i][j] = stoi(st.nextToken());
			}
		}
		dfs(0,0,new boolean[N][M], 0);
		System.out.println(answer);
	}

	static void dfs(int r, int c, boolean visit[][], int sum) {
		if (r == N - 1) {
			answer=Math.max(answer, sum);
			return;
		}
		boolean copyvisit[][] = new boolean[N][M];
		for (int i = 0; i < 5; i++) {
			for (int j = 0; j < N; j++)
				copyvisit[j] = Arrays.copyOf(visit[j], M);
			int tempsum=isValid(i, r, c, copyvisit);
			if(tempsum > -1) {
				int nc=c+1==M-1?0:c+1;
				int nr=c+1==M-1?r+1:r;
				dfs(nr, nc, copyvisit, sum+tempsum);
			}
		}
	}

	static int isValid(int type, int r, int c, boolean visit[][]) {
		if (type == 0) {
			if (!visit[r][c] && !visit[r][c + 1] && !visit[r + 1][c + 1]) {
				visit[r][c] = true;visit[r][c + 1] = true;visit[r + 1][c + 1] = true;
				return map[r][c]+(2*map[r][c+1])+map[r+1][c+1];
			} 
		} 
		else if (type == 1) {
			if (!visit[r][c + 1] && !visit[r + 1][c + 1] && !visit[r + 1][c]) {
				visit[r][c + 1] = true;visit[r + 1][c + 1] = true;visit[r + 1][c] = true;
				return map[r][c+1]+(2*map[r+1][c+1])+map[r+1][c];
			}
		}
		else if (type == 2) {
			if (!visit[r][c] && !visit[r + 1][c] && !visit[r + 1][c + 1]) {
				visit[r][c] = true;visit[r + 1][c] = true;visit[r + 1][c + 1] = true;
				return map[r][c]+(2*map[r+1][c])+map[r+1][c+1];
			}
		}
		else if (type == 3) {
				if (!visit[r][c] && !visit[r + 1][c] && !visit[r][c + 1]) {
					visit[r][c] = true;visit[r + 1][c] = true;visit[r][c + 1] = true;
					return (2*map[r][c])+map[r+1][c]+map[r][c+1];
				}
		} 
		else if (type == 4) {
				return 0;
			}
		return -1;
	}

	static int stoi(String s) {
		return Integer.valueOf(s);
	}
}