BOJ) NM과 K (1)

NM과 K (1)

18290번: NM과 K (1)

풀이

 

N x M의 격자판에서 k개를 선택하여, 해당 칸의 수를 더했을 때 최대 값이 되는 경우를 찾는 문제다.

또한 k 개를 선택할 때, 특정 좌표의 상하좌우로 인접해있으면 안된다는 조건이 있었다.

두 조건에 따라서 코드를 짜내려갔다.

 

방문체크를 하면서, 방문한 적이 없는 경우 상하좌우를 체크해주고, 선택이 가능한 경우면 sum에 더해서 다시 탐색하도록 했다.

k 개 만큼 선택을 했을 때, 최대 값을 비교하면서 최신화 해주며 답을 구했다.

 

여기서 실수했던 점은, 답이 되는 answer를 0으로 초기화 했던 것이다. 96%에서 틀리길래 뭐가 틀렸나 몇 번 생각하다 보니까,

격자판에 음의 정수가 들어가는 경우도 있음을 확인했다.

그래서 Integer의 MIN_VALUE로 초기화 해주니까 통과됐다.

 

문제를 꼼꼼하게 읽어야하는데.. 습관인가보다... ㅠㅠ

 

그리고, 아쉬운 점은 재귀 함수를 돌기 시작할 때, 모든 좌표를 다 돈다는 점이다.

파라메터가 많아서 시작점이 될 x와 y를 따로 담아주지 않았는데, 이 때문에 시간이 오래 걸리는 것 같다.

맵이나 n,k 등을 전역변수로 빼고 파라메터에 x,y좌표를 전달해주는 것이 더 좋아보인다.

 

코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class NMK_18290 {
    final static int[] dx = {1,0,-1,0}, dy = {0,1,0,-1};
    static int answer;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        int[][] map = new int[n+2][m+2];

        for(int i=1; i<=n; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=1; j<=m; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        solution(n,m,k,map);

        br.close();
    }

    private static void solution(int n, int m, int k, int[][] map) {
        answer =Integer.MIN_VALUE;  // 0으로 초기화 했어서 틀림,, 답이 -인 경우도 생각하자
        getMaxNum(n,m,k,map,new boolean[n+2][m+2], 0);
        System.out.println(answer);
    }

    private static void getMaxNum(int n, int m, int k, int[][] map, boolean[][] visit, int sum) {
        if(k ==0) {
            answer = Math.max(answer,sum);
            return;
        }
        for(int y=1; y<=n; y++) {
            for(int x=1; x<=m; x++) {
                if(!visit[y][x]) {  // 방문한 적 없으면
                    if(canPickNum(x,y,visit)) { // 고를 수 있으면
                        visit[y][x] = true; // 방문 체크
                        getMaxNum(n, m, k - 1, map, visit, sum + map[y][x]);
                        visit[y][x] = false;    // 방문 해제
                    }
                }
            }
        }
    }

    private static boolean canPickNum(int x, int y, boolean[][] visit) {
        boolean result = true;
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(visit[ny][nx]) {
                result = false;
            }
        }
        return result;
    }
}