[백준] 18290번 : NM과 K(1) (JAVA)

1. 문제 분석

 

격자내에서 이동하는 문제는 DFS로 많이 풀었었는데, 이건 조금 결이 다르다고 느껴졌다. 인접한 칸을 제외하고 K개의 칸에 수를 합해서 최댓값을 구하면 된다. 결국 전부 해봐야되는건 맞는거 같은데 어떻게 더할 것인가가 핵심이다. 시간 초과가 되지 않게 모든 경우의 수를 계산해보고 최댓값을 구하면 된다. 필자는 백트래킹을 활용해서 풀었다. N,M,K의 수가 크지 않기에 아래의 복잡도가 되어도 1초가 넘지 않는다.

 

시간복잡도 : O((NxM)^K)

알고리즘 : 백트래킹

2. 문제 풀이

백트래킹 부분을 슈도코드로 작성하면 다음과 같다. 

static void backtracking(int count, int row, int col, int sum){
	
    // K개의 노드를 골랐을 때 최댓값이면 정답 갱신
    if(count == K){
    	answer = Max(answer, sum);
    }
    
    for(int i = row; i < N; i++){
    	for(int j = (i==row ? col : 0){
        	// 상하좌우가 선택된 노드가 없을 때 실행
        	if(valid){	
            	vistited[i][j] = true;
	        backtracking(count + 1, i, j, sum + currentNode);
    	        vistited[i][j] = false;
            }
        }
    }

}

 

K개의 노드 값을 골랐으면 현재까지 나온 최댓값과 비교해서 갱신하고, 아직 K개를 고르지 못했다면 새로운 노드를 고른다. 만약 해당 노드의 상하좌우 중 선택된 노드가 있다면 이전으로 돌아가 다시 노드를 선택하는 알고리즘이다.

 

3. 코드 구현

public class Main {

    static int[][] map;
    static boolean[][] visited;
    static int N, M, K, answer;
    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());
        K = Integer.parseInt(st.nextToken());
        answer = Integer.MIN_VALUE;

        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());
            }
        }

        backtrack(0,0,0,0);

        System.out.println(answer);

    }

    static void backtrack(int count, int row, int col, int currentSum){

        if(count == K){
            answer = Math.max(currentSum, answer);
            return;
        }

        for(int i = row; i < N; i++){
            for(int j = (i == row ? col : 0); j < M; j++){
                if(isValid(i,j)){
                    visited[i][j] = true;
                    backtrack(count+1, i, j, currentSum + map[i][j]);
                    visited[i][j] = false;
                }
            }
        }
    }

    static boolean isValid(int x, int y){
        if(visited[x][y]) return false;
        if(x > 0 && visited[x-1][y]) return false;
        if(x < N-1 && visited[x+1][y]) return false;
        if(y > 0 && visited[x][y-1]) return false;
        if(y < M-1 && visited[x][y+1]) return false;
        return true;
    }
}