18290번 NM과 K (1)

문제:

• 문제 링크

크기가 N×M인 격자판의 각 칸에 정수가 하나씩 들어있다. 이 격자판에서 칸 K개를 선택할 것이고, 선택한 칸에 들어있는 수를 모두 더한 값의 최댓값을 구하려고 한다. 단, 선택한 두 칸이 인접하면 안된다. r행 c열에 있는 칸을 (r, c)라고 했을 때, (r-1, c), (r+1, c), (r, c-1), (r, c+1)에 있는 칸이 인접한 칸이다.

입력:

첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 N개의 줄에 격자판에 들어있는 수가 주어진다.

출력:

선택한 칸에 들어있는 수를 모두 더한 값의 최댓값을 출력한다.

접근 방법

1. 브루트포스로 모든 가능성을 따지는게 좋아보임
2. 백트래킹을 통해 K개를 선정해서 최대값을 비교하는 백트래킹을 구현

코드

접기/펼치기

import java.util.*;

public class NM과_K_1
{
    static int n , m , k;
    static int map[][];
    static boolean checkMap[][];

    static int maxValue = Integer.MIN_VALUE;
    static int curValue =0;
    public static void main(String [] args)
    {

        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        k = sc.nextInt();

        map = new int[n][m];
        checkMap = new boolean [n][m];
        for(int i = 0 ; i < n ; i ++)
        {
            for(int j = 0 ; j < m ; j ++)
            {
                map[i][j] = sc.nextInt();
            }
        }

        for(int i = 0 ; i < n ; i++)
        {
            for(int j = 0 ; j < m ; j++)
            {

                findMax(i,j,1);
            }
        }

        System.out.println(maxValue);
    }

    static int dx[] = {1,0,-1,0};
    static int dy[] = {0,1,0,-1};
    public static void findMax(int X,int Y,int t)
    {
        checkMap[X][Y] = true;
        curValue += map[X][Y];
        if(t == k)
        {
            if(maxValue < curValue) maxValue = curValue ;

        }

        else
       {
        for(int i = 0 ; i < n ; i ++)
        {
            for(int j = 0 ; j < m ; j++)
            {
                if(!checkMap[i][j]&&isValid(i,j))
                {
                    findMax(i, j, t+1);
                }
            }
        }}

        curValue -= map[X][Y];
        checkMap[X][Y] = false;

    }
    public static boolean isValid(int x , int y)
    {
        for(int i = 0 ; i < 4 ; i ++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx>=0 && ny >= 0 && nx < n && ny < m && checkMap[nx][ny])
            {
                return false;
            }
        }
        return true;
    }
}

처음에 백트래킹할 때 재귀를 거치면서 방문표시가 해제되면 안되는 상황에서 방문표시가 해제되어 버리는 경우가 발생했었다. 이 경우를 해결하기 위해 방문한 위치만 방문표시하는 로직으로 변경하였다.
지식이 늘었다.