SW 역량테스트 - [백준] 치킨 배달 문제 풀이/해답/코드 (C++ / JAVA)

---

SW 역량 테스트 준비를 위한 핵심 문제들을 다룹니다!

해답을 보기 전에 문제를 풀어보시거나, 설계를 하고 오시는 것을 추천드립니다. 

코드에 대한 설명은 주석을 참고해 주세요 :)

 

---

문제 링크 : www.acmicpc.net/problem/15686

해답 코드 : 

 

// java

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

class Pos {
    int r;
    int c;
    boolean visit;

    Pos(int x, int y) {
        r = x;
        c = y;
        visit = false;
    }
}

public class Main {

    // num_M is total "2" in the input "map"
    static int N, M, num_M;
    static int map[][];
    static int min_distance;

    static ArrayList<Pos> stores;
    static ArrayList<Pos> people;



    static int abs(int x) {
        if (x < 0) return (-1 * x);
        else return x;
    }

    static int dist(Pos x, Pos y) {
        return (abs(x.r-y.r) + abs(x.c-y.c));
    }

    static int dist(int r, int c, Pos y) {
        return (abs(r-y.r) + abs(c-y.c));
    }

    static void copy_map(int[][]dest, int[][]src) {

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                dest[i][j] = src[i][j];
            }
        }
    }

    // destroy stores and compute total minimum distance
    static void compute_dist() {

        int dist_sum = 0;
        int min_dist;

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

            min_dist = Integer.MAX_VALUE;

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

                if (stores.get(j).visit) {
                    int temp_dist = dist(people.get(i), stores.get(j));

                    if (min_dist > temp_dist) {
                        min_dist = temp_dist;
                    }
                }

            }

            dist_sum += min_dist;
        }

        if (min_distance > dist_sum) {
            min_distance = dist_sum;
        }

    }

    // decide which store would be closed
    static void allocate(int store, int last) {

        if (store == M) {
            compute_dist();
            return;
        }


        for (int i = last; i < stores.size(); i++) {

            stores.get(i).visit = true;

            allocate(store+1, last+1);

            stores.get(i).visit = false;

        }


    }





    public static void main(String args[]) {

        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();
        M = sc.nextInt();

        map = new int[N][N];
        people = new ArrayList<>();
        stores = new ArrayList<>();
        min_distance = Integer.MAX_VALUE;

        num_M = 0;

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {

                map[i][j] = sc.nextInt();

                if (map[i][j] == 1) {
                    people.add(new Pos(i, j));
                }
                else if (map[i][j] == 2) {
                    stores.add(new Pos(i, j));
                }
            }
        }


        allocate(0, 0);

        System.out.println(min_distance);

    }

}

 

SW 역량테스트 준비 - [모의 SW 역량테스트] 풀이 / 코드 / 답안 (C++ / JAVA)

SW 역량테스트 준비 - C++ 코드, Java 코드

SW 역량테스트 준비 - 백준 알고리즘 문제