[백준 18290, 자바] NM과 K (1) renew

문제풀이

 

"칸을 뽑는다"라는 행위가 반복된다. 이 행위가 언제까지 반복되는지를 보면, 현재까지 뽑은 칸의 갯수(pickCount)가 뽑아야하는 칸의 갯수(K)와 같아질 때까지 반복한다. pickCount와 K가 같으면, 현재까지의 칸의 합과 max 값을 비교하면 된다. 

 

 위의 로직을 재귀함수로 짰을 때의 구조는 아래와 같다. 

public static void pickCell(int pickCount, int sum) {
	if(pickCount>K) {
		return;
	}
	else if(pickCount ==K) {
		//최댓값과 현재까지의 합을 비교한다 
	}
	else {
		//칸을 뽑는다 
	}
}

 

이제 칸을 뽑는 경우를 생각해보자. 현재 호출된 함수에서 뽑을 수 있는 칸을 생각해보자. 재귀함수를 가지치기라고 생각한다면 현재 가지에서 뽑을 수 있는 칸은 이전 가지에서 뽑은 칸과 관련이 있다. 

 현재 가지에서 뽑을 수 있는 칸은, 이전 가지에서 뽑은 행,열을 기준으로 그 이후 부터 뽑을 수 있다. 

따라서 이전가지에서 뽑은 열, 행의 정보를 받아오고서 이 이후의 칸이 현재가지에서 뽑을 수 있는 칸의 후보가 된다. 이 후보가 되는 칸이 뽑을 수 있는 경우라면 뽑으면 된다. 

public static void pickCell(int pickCount, int pickedR, int pickedC, int sum) {
	if(pickCount>K) {
		return;
	}
	else if(pickCount ==K) {
		//최댓값과 현재까지의 합을 비교한다 
	}
	else {
		//칸을 뽑는다 
		for(int r=pickedR; r<N; r++) {
			for(int c=(r==pickedR? pickedC : 0); c<N; c++) {
				if(canpick(r,c)) {
					picked[r][c] = true;
					
					pickCell(pickCount+1, r,c,sum+map[r][c]);
					pciked[r][c] = false;
				}
			}
		}
	}
}

 

 

 

그럼 이 후보중에 뽑을 수 있는 경우를 생각해보자. 문제에서 "단, 선택한 두 칸이 인접하면 안된다" 선택한 두 칸이 인접하면 안된다고 했다. 

 

위의 경우를 구현하면 아래와 같다. 

public static boolean canpick(int r, int c) {
	if(picked[r][c]) {
		return false;
	}
	else {
		for(int d =0; d<4; d++) {
			int nx = r + dx[d];
			int ny = c + dy[d];
			
			if(nx>=0 && nx<N && ny>=0 && ny<M) {
				if(picked[nx][ny]) {
					return false;
				}
			}
		}
		return true;
	}
	
}

 

 

최종 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Baekjoon18290 {
	static int N;
	static int M;
	static int K;
	static int[][] map;
	static boolean[][] picked;
	static int[] dx = {-1,0,1,0};
	static int[] dy = {0,1,0,-1};
	static int max = Integer.MIN_VALUE;
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		
		map = new int[N][M];
		picked = new boolean[N][M];
		
		for(int r=0; r<N; r++) {
			st = new StringTokenizer(br.readLine()," ");
			for(int c=0; c<M; c++) {
				map[r][c] = Integer.parseInt(st.nextToken());
			}
		}
		
		pickCell(0,0,0,0);
		bw.write(String.valueOf(max));
		bw.flush();
		
		
	}
	
	public static void pickCell(int pickCount, int pickedR, int pickedC, int sum) {
		if(pickCount>K) {
			return;
		}
		else if(pickCount ==K) {
			//최댓값과 현재까지의 합을 비교한다
			max = Math.max(max, sum);
		}
		else {
			//칸을 뽑는다 
			for(int r=pickedR; r<N; r++) {
				for(int c=(r==pickedR? pickedC : 0); c<N; c++) {
					if(canpick(r,c)) {
						picked[r][c] = true;
						
						pickCell(pickCount+1, r,c,sum+map[r][c]);
						picked[r][c] = false;
					}
				}
			}
		}
	}
	
	public static boolean canpick(int r, int c) {
		if(picked[r][c]) {
			return false;
		}
		else {
			for(int d =0; d<4; d++) {
				int nx = r + dx[d];
				int ny = c + dy[d];
				
				if(nx>=0 && nx<N && ny>=0 && ny<M) {
					if(picked[nx][ny]) {
						return false;
					}
				}
			}
			return true;
		}
		
	}

}

 

재귀함수 부분 수정

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static int M;
    static int K;
    static int[][] map;
    static boolean[][] visted;
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        map = new int[N][M];
        for(int r=0; r<N; r++){
            st = new StringTokenizer(br.readLine(), " ");
            for(int c=0; c<M; c++){
                map[r][c] = Integer.parseInt(st.nextToken());
            }
        }
        visted = new boolean[N][M];
        int result = getMax(0, 0, 0, 0);
        bw.write(String.valueOf(result));
        bw.flush();


    }
    public static int getMax(int beforeR, int beforeC, int sum, int pickCount){
        if(pickCount>K){
            return Integer.MIN_VALUE;
        }
        else if(pickCount ==K){
            return sum;
        }
        else{
            int max = Integer.MIN_VALUE;
            for(int r = beforeR; r<N; r++){
                for(int c= (r==beforeR)? beforeC : 0; c<M; c++){
                    if(canPick(r,c)){
                        visted[r][c] = true;
                        int result = getMax(r, c, sum+map[r][c], pickCount+1);
                        visted[r][c] = false;

                        max = Math.max(max,result);
                    }
                }
            }
            return max;
        }
    }

    public static boolean canPick(int r, int c){
        if(visted[r][c]){
            return false;
        }
        else{
            for(int d=0; d<4; d++){
                int nx = r + dx[d];
                int ny = c + dy[d];

                if(nx>=0 && nx<N && ny>=0 && ny<M){
                    if(visted[nx][ny]){
                        return false;
                    }
                }
            }
            return true;
        }
    }
}