[Softeer] 함께하는 효도 / Java

문제 출처

https://softeer.ai/practice/7727

Softeer - 현대자동차그룹 SW인재확보플랫폼

문제 풀이

완전탐색으로 문제를 풀이해보았습니다.

주어진 조건에 따르면 친구의 수가 최대 3 명이고 최대로 이동할 수 있는 횟수가 3 번뿐이기에 모든 경우의 수를 탐색해볼만 하다고 생각했습니다.

 

따라서 아래와 같은 순서에 따라 코드를 구성하였습니다.

1. 순열(Permutation)로 각 친구가 움직일 수 있는 모든 경로(Route)를 구한다.

2. 조합(Combination)으로 각 친구가 어떤 경로를 선택했는지에 대한 모든 경우의 수를 탐색하며 최대 수확량을 구한다.

 

추가적인 설명은 코드 내의 주석으로 작성하였습니다.

Java Code

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

public class Main {

    static final int AVAILABLE_TIME = 4;  // 최대로 방문할 수 있는 칸의 수
    static int N, M;
    static int[][] map;
    static int[] di = {-1, 1, 0, 0};
    static int[] dj = {0, 0, -1, 1};
    static Point[] friendPoints;  // 각 친구의 시작 지점
    static List<List<Route>> friendsRoutes;  // 각 친구가 가지는 루트 목록
    static List<Point> visitedPoints = new ArrayList<>();  // 방문한 지점 목록
    static Route[] routesComb;  // 루트의 조합으로 만들어낸 하나의 경우
    static int maxResult = 0;  // 최대 열매 수확량
    static class Point {
        int x, y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public boolean equals(Point point) {
            return x == point.x && y == point.y;
        }
    }
    static class Route {
        Point[] points;

        public Route(List<Point> points) {
            this.points = points.toArray(new Point[AVAILABLE_TIME]);
        }
    }

    /**
     * 입출력
     */
    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());
        map = new int[N][N];
        for (int i = 0; i < N; i++) {
            map[i] = Arrays.stream(br.readLine().split(" "))
                .mapToInt(Integer::parseInt).toArray();
        }

        friendPoints = new Point[M];
        friendsRoutes = new ArrayList<>();
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken()) - 1;
            int y = Integer.parseInt(st.nextToken()) - 1;

            friendPoints[i] = new Point(x, y);
            friendsRoutes.add(new ArrayList<>());
        }

        routesComb = new Route[M];

        solution();

        System.out.println(maxResult);
    }

    public static void solution() {
        // 모든 친구의 루트 탐색
        findAllFriendRoutes();

        // 각 친구의 루트의 조합
        findRouteCombination(0);
    }

    /**
     * 모든 친구들에 대해 각자가 가질 수 있는 루트의 경우의 수 탐색
     */
    public static void findAllFriendRoutes() {
        for (int i = 0; i < M; i++) {
            visitedPoints.add(friendPoints[i]);
            findEachFriendRoutes(i, friendPoints[i]);
            visitedPoints.clear();  // 다음 친구의 방문을 기록하기 위해 현재 친구의 방문 기록을 초기화
        }
    }

    /**
     * 한 친구가 갈 수 있는 모든 루트 탐색
     * @param friendIdx 친구 인덱스
     * @param curPoint 친구의 시작 지점
     */
    public static void findEachFriendRoutes(int friendIdx, Point curPoint) {
        if (visitedPoints.size() == AVAILABLE_TIME) {  // 최대 범위에 다다른 경우
            friendsRoutes.get(friendIdx).add(new Route(visitedPoints));  // 현재 친구의 인덱스에 루트를 저장
            return;
        }

        for (int d = 0; d < 4; d++) {
            int ni = curPoint.x + di[d];
            int nj = curPoint.y + dj[d];

            if (ni < 0 || nj < 0 || ni >= N || nj >= N) continue;

            Point newPoint = new Point(ni, nj);
            if (isVisited(visitedPoints, newPoint)) continue;  // 이미 방문한 지점인 경우

            visitedPoints.add(newPoint);
            findEachFriendRoutes(friendIdx, newPoint);
            visitedPoints.remove(visitedPoints.size() - 1);
        }
    }

    /**
     * point가 이미 방문한 지점인지 여부를 반환
     * @param visitedPoints 지금까지 방문한 지점들
     * @param point 현재 지점
     * @return 방문 여부
     */
    public static boolean isVisited(List<Point> visitedPoints, Point point) {
        for (Point visitedPoint : visitedPoints) {
            if (visitedPoint.equals(point)) return true;
        }
        return false;
    }

    /**
     * 각 친구가 갈 수 있는 루트들의 모든 조합 탐색
     * @param friendIdx 탐색할 친구의 인덱스
     */
    public static void findRouteCombination(int friendIdx) {
        if (friendIdx == M) {
            maxResult = Math.max(maxResult, getTotalFruits());  // 최대 수확량 갱신
            return;
        }

        for (Route route : friendsRoutes.get(friendIdx)) {
            routesComb[friendIdx] = route;
            findRouteCombination(friendIdx+1);
        }
    }

    /**
     * 각 경우의 수에서 얻을 수 있는 열매 수확량 계산
     * @return 열매 수확량
     */
    public static int getTotalFruits() {
        int result = 0;

        boolean[][] visited = new boolean[N][N];
        for (Route route : routesComb) {
            for (Point point : route.points) {
                if (visited[point.x][point.y]) continue;  // 이미 카운트한 칸은 중복 카운트하지 않는다

                visited[point.x][point.y] = true;
                result += map[point.x][point.y];
            }
        }

        return result;
    }

}