취미처럼

[백준] 18290번 NM과 K (1) 본문

Algorithm/백준

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

sirius 2021. 3. 3. 09:51
https://www.acmicpc.net/problem/18290
 

18290번: NM과 K (1)

크기가 N×M인 격자판의 각 칸에 정수가 하나씩 들어있다. 이 격자판에서 칸 K개를 선택할 것이고, 선택한 칸에 들어있는 수를 모두 더한 값의 최댓값을 구하려고 한다. 단, 선택한 두 칸이 인접

www.acmicpc.net

 

처음에 인접하지 않은 칸의 수의 합이라 하여 대각선을 더한 값이라고 생각하였으나 

2칸 이상 떨어져도 인접하지 않은 칸이니 모두 탐색하여야 함

이미 탐색한 좌표를 다시 탐색하지 않기 위해 방문여부 체크

checkMove() 에서 인접한 좌표를 이미 방문하였다면 false리턴하여 다음 좌표로 넘어가게 함

 

 

import java.util.*;
import java.io.*;

public class Main {

    public static int N, M, K, max;
    public static int[][] arr;
    public static boolean[][] visit;

    public static int[] dy = {0, 1, 0, -1};
    public static int[] dx = {1, 0, -1, 0};

    public static void main(String[] args) throws Exception {

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

        arr = new int[N][M];
        visit = new boolean[N][M];
        max = Integer.MIN_VALUE;

        for(int y = 0; y < N; y++) {
            st = new StringTokenizer(br.readLine());
            for(int x = 0; x < M; x++) {
            	arr[y][x] = Integer.parseInt(st.nextToken());
        	}
        }
        dfs(0, 0, 0, 0);
        System.out.println(max);
    }

    public static void dfs(int y, int x, int depth, int sum) {
        if(depth == K) {
       		max = Math.max(max, sum);
            return;
        }
        for(int i = y; i < N; i++) {
            for(int j = x; j < M; j++) {
                if(!visit[i][j] && checkMove(i, j)) {
                    visit[i][j] = true;
                    dfs(y, x, depth + 1, sum + arr[i][j]);
                    visit[i][j] = false;
                }
            }
        }

    }

    // 인접한 좌표인지 체크
    public static boolean checkMove(int y, int x) {
        boolean flag = true;
        for(int i = 0; i < 4; i ++) {
            int ny = y + dy[i];
            int nx = x + dx[i];

            if(ny >= 0 && ny < N && nx >= 0 && nx < M) {
                if(visit[ny][nx]) {
                	flag = false;
           	 	}
            }

        }
        return flag;
    }


}

 

'Algorithm > 백준' 카테고리의 다른 글

[백준] 14501번 퇴사  (0) 2021.03.03
[백준] 1759번 암호 만들기  (0) 2021.03.03
[백준] 15657번 N과 M (8)  (0) 2021.03.03
[백준] 15656번 N과 M (7)  (0) 2021.03.03
[백준] 15655번 N과 M (6)  (0) 2021.03.03
Comments