[BFS/자바] 코드트리 IL. 우리는 하나

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

문제 해석

k개의 도시를 중복 없이 골라야 하므로, 백트래킹을 통해 k개의 도시를 선정한 뒤,

각 시작점으로부터 BFS를 통해 탐색을 해서 이동 수의 최대를 뽑아내면 된다.

u 이상 d 이하인 것을 검사하는 로직은 canGo()에서 검사하면 된다.

 

문제 풀이

• 백트래킹으로 k개의 도시를 고른다. (중복이 없어야 하므로 selected[][] 활용)
• 모든 경우를 탐색해야 하므로 적절하게 isVisited[][]를 초기화해줘야 한다.

import javax.swing.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    private static class Pair {
        private int x;
        private int y;

        private Pair(int y, int x) {
            this.x = x;
            this.y = y;
        }
    }

    private static boolean inRange(int y, int x) {
        return y >= 0 && y < n && x >= 0 && x < n;
    }

    private static boolean canGo(int y, int x, int prevY, int prevX) {
        return inRange(y, x) && canJump(y, x, prevY, prevX) && !isVisited[y][x];
    }

    private static boolean canJump(int y, int x, int prevY, int prevX) {
        int gap = Math.abs(cities[y][x] - cities[prevY][prevX]);
        return gap >= u && gap <= d;
    }

    private static void bfs() {
        int[] dx = new int[]{0, 1, 0, -1};
        int[] dy = new int[]{1, 0, -1, 0};

        while (!q.isEmpty()) {
            Pair crt = q.poll();
            for (int i = 0; i < 4; i++) {
                int newX = crt.x + dx[i];
                int newY = crt.y + dy[i];
                if (canGo(newY, newX, crt.y, crt.x)) {
                    isVisited[newY][newX] = true;
                    ans++;
                    q.add(new Pair(newY, newX));
                }
            }
        }
    }

    private static void go() {
        if (selected.size() == k) {
            for (Pair p : selected) {
                isVisited[p.y][p.x] = true;
                ans++;
                q.add(p);
            }
            bfs();
            pq.add(-ans);
            isVisited = new boolean[n][n];
            ans = 0;
            return;
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (!isSelected[i][j]) {
                    isSelected[i][j] = true;
                    selected.add(new Pair(i, j));
                    go();
                    isSelected[i][j] = false;
                    selected.remove(selected.size() - 1);
                }
            }
        }

    }

    private static int n, k, u, d;
    private static int ans = 0;

    private static int[][] cities;
    private static boolean[][] isSelected;
    private static boolean[][] isVisited;

    private static List<Pair> selected = new ArrayList<>();
    private static Queue<Pair> q = new LinkedList<>();
    private static Queue<Integer> pq = new PriorityQueue<>();


    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());
        k = Integer.parseInt(st.nextToken());
        u = Integer.parseInt(st.nextToken());
        d = Integer.parseInt(st.nextToken());
        cities = new int[n][n];
        isVisited = new boolean[n][n];
        isSelected = new boolean[n][n];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                cities[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        go();
        System.out.println(-pq.poll());
    }
}