백준 18290번 : NM과 K (1)(Java)

https://www.acmicpc.net/problem/18290

18290번: NM과 K (1)

---

[풀이]

• 백트래킹 및 DFS를 이용하여 풀었습니다.
• answer 변수는 주어지는 배열의 값이 음수가 입력될 수 있으므로 Integer.MIN_VALUE를 이용했습니다.
• check() 메소드에서, 이동하는 위치의 값이 인접한 곳일 경우(상하좌우), boolean 값을 false로 반환하여 이동하지 못하도록 했습니다.
• 재귀형식의 메소드 실행 횟수가 K 변수와 같아진다면 answer 변수의 최대값을 구하도록 했습니다.
• 반복문 내에서는 두가지를 확인하면서 진행했습니다.
  • 이전에 구현해놓은 check()메소드를 통하여 인접한지 확인하여 인접하지 않을 경우에만 재귀를 실행하도록 했습니다.
  • visited 2차원 배열을 통해 방문하지 않은 곳만 탐색하도록 했습니다.

---

[코드]

 

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

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

    public static void solve(int x, int y, int idx, int sum) {
        if (idx == K) {
            answer = Math.max(answer, sum);
            return;
        } else {
            for (int i = x; i < N; i++) {
                for (int j = y; j < M; j++) {
                    if (!visited[i][j]) {
                        if (check(i, j)) {
                            visited[i][j] = true;
                            solve(x, y, idx + 1, sum + arr[i][j]);
                            visited[i][j] = false;
                        }
                    }
                }
            }
        }

    }

    public static boolean check(int x, int y) {
        boolean flag = true;
        for (int i = 0; i < 4; i++) {
            int next_x = x + dx[i];
            int next_y = y + dy[i];

            if (next_x >= 0 && next_x < N && next_y >= 0 && next_y < M) {
                if (visited[next_x][next_y]) {
                    flag = false;
                }
            }
        }
        return flag;
    }

    public static void main(String[] args) throws IOException {
        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];
        visited = new boolean[N + 1][M + 1];
        answer = Integer.MIN_VALUE;

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < M; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        solve(0, 0, 0, 0);
        System.out.println(answer);
    }
}