[자바로 푸는 백준] 18430번 무기 공학

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

18430번: 무기 공학

✅ 골드 Ⅳ

 

🔶 풀이

N x M 크기의 고급 나무 재료가 주어졌을 때, 'ㄱ'자 모양 부메랑들의 강도 합이 최댓값을 구하라.

N과 M의 크기가 작으므로 완전 탐색으로 해결할 수 있다.

 

우선 백트래킹을 사용하기 위해서 dfs를 이용한다.

idx를 0부터 순차적으로 늘리면서 좌표값 (x, y)를 제어해 줬다.

int x = idx/M;
int y = idx%M;

 

idx가 N*M에 도달하면 모든 좌표를 탐색한 것으로 현재 좌표에서 부메랑 4개 모양을 만들 수 있는 확인 해준다.

범위를 벗어나거나 이미 방문한 경우를 제외하고, 부메랑이 만들어졌다면 (부메랑 날개좌표값 1 + 부메랑 날개좌표값 2 + 해당 좌표값 * 2) 을 해주면서 idx를 1 증가시켜 주면 된다.

 

이후에 모든 좌표를 탐색했을 경우 최댓값을 찾아주면 완료.

 

<최종코드>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static int N, M, ans;
    static int[][] map;
    static boolean[][] visited;
	
    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());
		
        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());
            }
        }
		
        findBoomerang(0, 0);
        System.out.println(ans);
    }
	
    public static void findBoomerang(int idx, int tmpSum) {
        if (idx == N*M) {
            ans = Math.max(ans, tmpSum);
            return;
        }
		
        int x = idx/M;
        int y = idx%M;
		
        if (!visited[x][y]) {
            // ┑
            if (x+1 < N && y-1 >= 0 && !visited[x+1][y] && !visited[x][y-1]) {
                visited[x+1][y] = true;
                visited[x][y] = true;
                visited[x][y-1] = true;
                findBoomerang(idx+1, tmpSum + map[x+1][y] + map[x][y-1] + (map[x][y]*2));
                visited[x+1][y] = false;
                visited[x][y] = false;
                visited[x][y-1] = false;
            }
            // ┙
            if (x-1 >= 0 && y-1 >= 0 && !visited[x-1][y] && !visited[x][y-1]) {
                visited[x-1][y] = true;
                visited[x][y] = true;
                visited[x][y-1] = true;
                findBoomerang(idx+1, tmpSum + map[x-1][y] + map[x][y-1] + (map[x][y]*2));
                visited[x-1][y] = false;
                visited[x][y] = false;
                visited[x][y-1] = false;
            }
            // ┕
            if (x-1 >= 0 && y+1 < M && !visited[x-1][y] && !visited[x][y+1]) {
                visited[x-1][y] = true;
                visited[x][y] = true;
                visited[x][y+1] = true;
                findBoomerang(idx+1, tmpSum + map[x-1][y] + map[x][y+1] + (map[x][y]*2));
                visited[x-1][y] = false;
                visited[x][y] = false;
                visited[x][y+1] = false;
            }
            // ┍
            if (x+1 < N && y+1 < M && !visited[x+1][y] && !visited[x][y+1]) {
                visited[x+1][y] = true;
                visited[x][y] = true;
                visited[x][y+1] = true;
                findBoomerang(idx+1, tmpSum + map[x+1][y] + map[x][y+1] + (map[x][y]*2));
                visited[x+1][y] = false;
                visited[x][y] = false;
                visited[x][y+1] = false;
            }
        }
		
        findBoomerang(idx+1, tmpSum);
    }
}