문제 링크

문제에서는 서로 다른 위치에서 동시에 출발을 하는 것으로 적혀있어 이 부분을 어떻게 해야할 지 많은 고민이 되었다. 고민을 하다보니 그냥 동시에 출발한다고 생각하지 않고, 한 명이 먼저 출발을 한 후에 3초 동안 수확할 수 있는 최대 값을 구하고 방문 처리를 한 후 다음 사람을 출발 시켜서 최대값을 구하고 이런 식으로 풀이하면 될 거 같았다.

풀이 1 (틀림)

친구들의 시작 좌표를 큐에 담고 한명씩 출발하여 3초가 지나면 poll()을 통해 이미 수확을 완료한 친구를 큐에서 제거하고 다음 사람을 출발 시키는 방식으로 구현을 하였다. 이렇게 풀이하니 운이 좋은건지 나쁜건지 예제로 나와있는 테스트 케이스를 통과하는 바람에 왜 틀렸나 한참을 고민하게 되었다. 해당 방식은 각 친구들마다 최댓값의 합이 전체 최댓값과 같다는 가정하에는 맞는 풀이이지만 실제로는 아니기 때문에 틀린 풀이이다.

코드 1 (틀림)

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

public class Main {

    static int n, m;
    static int[][] map;
    static boolean[][] visited;
    static Queue<Position> fPositions;
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};
    static int result = Integer.MIN_VALUE;

    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];
        visited = new boolean[n][n];
        fPositions = new LinkedList<>();

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        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;
            fPositions.add(new Position(x, y));
        }
        Position start = fPositions.poll();
        backTracking(start, 0, map[start.x][start.y]);
        System.out.println(result);
    }

    public static void backTracking(Position start, int time, int sum) {
        visited[start.x][start.y] = true;
        if (time == 3) {
            if (fPositions.isEmpty()) {
                result = Math.max(sum, result);
            } else {
                Position next = fPositions.poll();
                backTracking(next, 0, sum + map[next.x][next.y]);
            }
        } else {
            for (int i = 0; i < 4; i++) {
                int nx = start.x + dx[i];
                int ny = start.y + dy[i];
                if ((nx >= 0 && nx < n) && (ny >= 0 && ny < n) && !visited[nx][ny]) {
                    visited[nx][ny] = true;
                    backTracking(new Position(nx, ny), time + 1, sum + map[nx][ny]);
                    visited[nx][ny] = false;
                }
            }
        }
    }
    
    public static class Position {
        int x, y;

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

풀이 2

결국 한명씩 출발하는 것은 유지하되, 한명의 최댓값을 찾고 poll로 아예 제거하는 것이 아닌 이어서 출발시킨다는 생각으로 모든 경우의 수를 찾아 최댓값을 찾아내야한다. 따라서 친구 목록을 계속 유지해야한다. 큐를 사용하는 것이 아닌 리스트로 관리를 해야한다.

코드 2

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

public class Main {

    static int n, m;
    static int[][] map;
    static boolean[][] visited;
    static List<Position> friends;
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};
    static int result = Integer.MIN_VALUE;

    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];
        visited = new boolean[n][n];
        friends = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        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;
            friends.add(new Position(x, y));
        }
        Position start = friends.get(0);
        backTracking(start, 0, 0, map[start.x][start.y]);
        System.out.println(result);
    }

    public static void backTracking(Position start, int friendIdx, int time, int sum) {
        visited[start.x][start.y] = true;
        if (time == 3) {
            if (friendIdx + 1 == m) {
                result = Math.max(sum, result);
            } else {
                Position next = friends.get(friendIdx + 1);
                backTracking(next, friendIdx + 1, 0, sum + map[next.x][next.y]);
            }
        } else {
            for (int i = 0; i < 4; i++) {
                int nx = start.x + dx[i];
                int ny = start.y + dy[i];
                if ((nx >= 0 && nx < n) && (ny >= 0 && ny < n) && !visited[nx][ny]) {
                    visited[nx][ny] = true;
                    backTracking(new Position(nx, ny), friendIdx, time + 1, sum + map[nx][ny]);
                    visited[nx][ny] = false;
                }
            }
        }
    }

    public static class Position {
        int x, y;

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