[백준] code.plus(브루트포스,JAVA)18290번, NM과 K(1)

문제 링크

18290번: NM과 K (1)

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

브루트 포스란.

모든 경우의 수를 대입시켜서 가장 알맞은 경우의 수를 결과로 출력하는 것입니다.

 

이 문제에서 비내림차순으로 M개 수를 가진 수열이 나올 수 있는 경우의 수를 구하는 것과 중복이 가능하다는 것이 핵심입니다.

 

배열

num : 격자판 값들을 저장합니다.

 

check : 격자판 값을 선택할 수 있는지 판단하는 값 저장

 

배열에 인접한 값들은 상하좌우로 이동한 값으로 아래 2개의 배열을 사용합니다.

dx[] = {-1, 1, 0 0}

dy[] = {0, 0, -1, 1}

[2][2]기준으로 상하좌우 이동하면상

2 + dx[0] = 2 + (-1) = 1

2 + dy[0] = 2 + (0) = 2

하

2 + dx[1] = 2 + (1) = 3

2 + dy[1] = 2 + (0) = 2

좌

2 + dx[2] = 2 + (0) = 2

2 + dy[2] = 2 + (-1) = 1

우

2 + dx[3] = 2 + (0) = 2

2 + dy[3] = 2 + (1) = 3

0,0	0,1	0,2	0,3
1,0	1,1	1,2(상)	1,3
2,0	2,1(좌)	2,2(기준)	2,3(우)
3,0	3,1	3,2(하)	3,3

 

위에 check, num, dx, dy와 재귀를 통해 최대값을 구하였습니다.

 

문제에 해결알고리즘은

1. num 배열을 오름차순 정렬합니다.

2. 재귀를 통해 수열에 들어갈 수 있는 경우의 수를 찾습니다.

3. 수열 들어간 숫자들은 result[]에 저장합니다.

4. 재귀가 M번 반복되었을 때 현재 수열이 저장된 result[]를 결과에 저장합니다.

5. 재귀 종료시 모든 경우의 수를 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 저장하였습니다.
• StringTokenizer를 이용하여 배열의 들어갈 수 있는 숫자들을 저장하였습니다.
• 모든 경우의 수의 최대값을 구하는NMandK 함수를 만들었습니다.
• 기준값에 인접한 선택된 값 확인하는 adjacent함수를 만들었습니다.
• BufferedWriter에 최대값을 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• NMandK는 재귀를 사용하여 모든 경우의 수에서 최대값을 구하였습니다.
• adjacent는 dx와 dy를 이용하여 인접한 선택된 값이 존재하는지 확인합니다.

 

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	public static int[][] num;	//격자판 값 저장 배열
	public static boolean[][] check;		//선택 가능한지 확인 함수
	public static int[] dx = {-1,1,0,0};	//상, 하, 좌, 우 x값
	public static int[] dy = {0,0,-1,1};	//상, 하, 좌, 우 y값
	public static int N,M,K, maxNum = Integer.MIN_VALUE;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
        //----------입력값 저장 및 배열 초기화--------
    	StringTokenizer st = new StringTokenizer(br.readLine()," ");
    	N = Integer.parseInt(st.nextToken());
    	M = Integer.parseInt(st.nextToken());
    	K = Integer.parseInt(st.nextToken());
    	num = new int[N][M];
    	check = new boolean[N][M];
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine()," ");
    		for(int j=0;j<M;j++) {
    			num[i][j] = Integer.parseInt(st.nextToken());
    		}
    	}
    	NMandK(0,0);	//함수 실행
    	bw.write(maxNum + "\n");	//최대값 BufferedWriter 저장
    	bw.flush();			//결과 저장
    	bw.close();
    	br.close();
    }
    //------재귀를 통해 모든 경우의 수의 최대값 구하는 함수--------
    public static void NMandK(int depth, int sum) {
    	if(depth==K) {		//모두 선택되었을 때
    		maxNum = Math.max(maxNum, sum);
    		return;
    	}
    	for(int i=0;i<N;i++) {
    		for(int j=0;j<M;j++) {
    			if(!check[i][j]) {	//선택되지 않았을 때
    	 			if(adjacent(i, j)) {	//인접한 선택된 값 없을 때
        				check[i][j] = true;
        				NMandK(depth+1, sum + num[i][j]);	//재귀
        				check[i][j] = false;
        			}
    			}
    		}
    	}
    }
    //--------기준값에 인접한 선택되었던 값 있는지 확인하는 함수--------
    public static boolean adjacent(int x, int y) {
    	for(int i=0;i<4;i++) {
    		int tempX = x + dx[i];	//상, 하, 좌, 우 x값 변경
    		int tempY = y + dy[i];	//상, 하, 좌, 우 y값 변경
    		if(tempX>=0 && tempX<N && tempY>=0 && tempY<M)
    			if(check[tempX][tempY])
    				return false;		//선택된 값 인접할 때
    	}
    	return true;		//인접한 선택된 값 없을 때
    }

}