[백준] 20208. 진우의 민트초코우유

문제 링크

[백준] 20208. 진우의 민트초코우유

풀이 과정

완전탐색 문제입니다.

for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
        int num = sc.nextInt();

        if (num == 1) house = new Point(i, j);
        else if (num == 2) milk.add(new Point(i, j));
    }
}

먼저 NXN 크기의 2차원 배열의 각 요소에 해당하는 값을 입력받습니다.

• 1은 집을 의미하므로, 변수 house 에 해당 좌표를 저장합니다.
• 2는 민트초코우유를 의미하므로, 리스트 milk 에 해당 좌표들을 저장합니다.

for (int i = 0; i < milk.size(); i++) {
    Point init = milk.get(i);
    int dist = Math.abs(house.x - init.x) + Math.abs(house.y - init.y);

    if (dist <= M) {
        solve(init, i, M - dist + H, 1);
    }
}

이제 모든 민트초코우유의 좌표가 저장되어 있는 milk 를 순회하며, 제일 처음으로 방문할 민트초코우유를 결정합니다.

그리고 초기 체력 M으로 집으로부터 해당 우유까지 도달할 수 있는지를 체크합니다. 도달할 수 있다면, 재귀 함수 solve 메소드 를 호출함으로써, 다음번 우유를 정하고 집으로 돌아갈 수 있는지에 대한 여부를 재귀적으로 확인합니다.

static void solve(Point now, int idx, int hp, int cnt) {
        visit[idx] = true;

        for (int i = 0; i < milk.size(); i++) {
            if (!visit[i]) {
                Point next = milk.get(i);
                int dist = Math.abs(now.x - next.x) + Math.abs(now.y - next.y);

                if (dist <= hp)
                    solve(next, i, hp - dist + H, cnt + 1);
            }
        }

        int dist = Math.abs(now.x - house.x) + Math.abs(now.y - house.y);

        if (dist <= hp) {
            answer = Math.max(answer, cnt);
        }

        visit[idx] = false;
    }

solve 메소드 는 현재 위치의 우유를 기준으로, 다음번에 방문할 우유를 정합니다.

• 먼저 현재 우유 now 에 대한 방문 처리를 합니다. 이는 다음번에는 해당 우유를 또다시 방문하지 않기 위함입니다.
• 이후에는 방문하지 않은 우유 next 를 하나 골라, 현재 체력 hp 로 도달할 수 있는지를 확인합니다. 도달할 수 있다면, 파라미터를 next 로 맞추고, 체력과 우유의 개수를 누적시켜 다음번 재귀 함수를 호출합니다.
• 다음은 현재 체력 hp 를 가지고 현재 방문한 우유의 좌표 now 에서 집으로 돌아갈 수 있는지를 확인해봅니다. 집으로 돌아갈 수 있고, 지금까지의 방문 우유 개수가 최대값이라면 갱신합니다.
• 다른 경우의 수를 위해, 현재 우유 now 에 대한 방문 처리를 되돌려줍니다.

코드

import java.awt.*;
import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    static int N, M, H;
    static int[][] map;
    static boolean[] visit;
    static Point house;
    static ArrayList<Point> milk;
    static int answer;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        H = sc.nextInt();
        map = new int[N][N];
        visit = new boolean[milk.size()];
        milk = new ArrayList<>();

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                int num = sc.nextInt();

                if (num == 1) house = new Point(i, j);
                else if (num == 2) milk.add(new Point(i, j));
            }
        }

        for (int i = 0; i < milk.size(); i++) {
            Point init = milk.get(i);
            int dist = Math.abs(house.x - init.x) + Math.abs(house.y - init.y);

            if (dist <= M) {
                solve(init, i, M - dist + H, 1);
            }
        }

        System.out.println(answer);
    }

    static void solve(Point now, int idx, int hp, int cnt) {
        visit[idx] = true;

        for (int i = 0; i < milk.size(); i++) {
            if (!visit[i]) {
                Point next = milk.get(i);
                int dist = Math.abs(now.x - next.x) + Math.abs(now.y - next.y);

                if (dist <= hp)
                    solve(next, i, hp - dist + H, cnt + 1);
            }
        }

        int dist = Math.abs(now.x - house.x) + Math.abs(now.y - house.y);

        if (dist <= hp) {
            answer = Math.max(answer, cnt);
        }

        visit[idx] = false;
    }
}

안된코드

package 완전탐색;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class BOJ_20208_진우의민트초코우유 {
    static int N, M, H;
    static int[] dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1};
    static int[][] map;
    static Point house;
    static ArrayList<Point> milk;
    static boolean[] visit;
    static int answer;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        H = sc.nextInt();
        map = new int[N][N];
        milk = new ArrayList<>();

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                int num = sc.nextInt();
                if (num == 1) {
                    house = new Point(i, j);
                } else if (num == 2) {
                    milk.add(new Point(i, j));
                }
            }
        }

        visit = new boolean[milk.size()];

        for (int i = 0; i < milk.size(); i++) {
            solve(house, i, M, 0);
        }

        System.out.println(answer);
    }

    static void solve(Point now, int idx, int hp, int cnt) {
        Point next = milk.get(idx);
        int dist = Math.abs(now.x - next.x) + Math.abs(now.y - next.y);

        if (dist <= hp) {
            visit[idx] = true;

            for (int i = 0; i < milk.size(); i++) {
                if (!visit[i]) {
                    solve(next, i, hp - dist + H, cnt + 1);
                }
            }

            visit[idx] = false;
        }

        dist = Math.abs(now.x - house.x) + Math.abs(now.y - house.y);

        if (dist <= hp) {
            answer = Math.max(answer, cnt);
        }
    }

    static class Point {
        int x, y;

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