글 읽기 - 하루넘게 고민중입니다 ㅠㅠ 한번 봐주시면 감사하겠습니다.

pl10hg 4년 전 0

예제에 있는 테스트 케이스 1,2 번은 틀리고 3,4,번은 맞게 나옵니다.

또한 질문 게시판에서 찾은 반례들도 일부는 맞고 일부는 틀리게 나오는데

당최 어디가 문제인지 하루넘게 고민중입니다 ㅠㅠ

조언좀 부탁드리겠습니다.

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

class Point {
    int x;
    int y;

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


public class Main {

    static ArrayList<Point> homes = new ArrayList<>();
    static ArrayList<Point> chickens = new ArrayList<>();
    static ArrayList<Point> selectedChiken = new ArrayList<>();
    static int[][] map;
    static int ans = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] input = br.readLine().split(" ");
        int n = Integer.parseInt(input[0]);
        int m = Integer.parseInt(input[1]); // 치킨집 최대 갯수

        map = new int[n][n];

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if (map[i][j] == 1) homes.add(new Point(i, j));
                if (map[i][j] == 2) chickens.add(new Point(i, j));
            }
        }

        dfs(0, 0, m);

        System.out.println(ans);
    }

    private static void dfs(int index, int select, int m) {

        if (index >= chickens.size()) return;

        if (select == m) {
            int tmpAns = 0;

            for (int i = 0; i < homes.size(); i++) {

                Point h = homes.get(i);
                int minDist = Integer.MAX_VALUE;

                for (int j = 0; j < selectedChiken.size(); j++) {

                    Point c = selectedChiken.get(j);
                    int dist = Math.abs(h.x - c.x) + Math.abs(h.y - c.y);

                    minDist = Math.min(minDist, dist);
                }
                tmpAns += minDist;
            }

            if (ans > tmpAns) {
                ans = tmpAns;
                return;
            }
        }

        // 치킨 배달집으로 선택
        selectedChiken.add(chickens.get(index));
        dfs(index + 1, select + 1, m);

        // 치킨 배달집으로 선택되지 않음
        selectedChiken.remove(selectedChiken.size() - 1);
        dfs(index + 1, select, m);
    }
}

djm03178 4년 전 0

답이 안 나오는 예시를 찾았다면, 가장 먼저 해봐야 할 것은 그 예시가 원래 어떻게 해서 답을 얻어내야 하는지 손으로 해보고, 자신의 코드가 그 과정을 올바르게 쫓아가는지 중간 과정을 단계별로 출력해 보는 것입니다. 그러면 도중 어딘가에서 처음으로 의도와 다르게 비껴가는 구간이 있겠죠? 그 지점에서부터 잘못된 곳을 찾아나가면 됩니다.

pl10hg 4년 전 0

문제 해결했습니다.

51번 라인을 76라인으로 바꾸니 해결되네요;;

함수종료 선언부 위치의 중요성을 간과했습니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

하루넘게 고민중입니다 ㅠㅠ 한번 봐주시면 감사하겠습니다.

pl10hg 4년 전 0

djm03178 4년 전 0

pl10hg 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말