백준 15686번 치킨 배달 [Java, Kotlin]

: ) YOUNG·2022년 5월 31일
2

알고리즘

목록 보기
140/417
post-thumbnail

백준 10819번
https://www.acmicpc.net/problem/15686

문제



이 도시에 있는 치킨집은 모두 같은 프랜차이즈이다. 프렌차이즈 본사에서는 수익을 증가시키기 위해 일부 치킨집을 폐업시키려고 한다. 오랜 연구 끝에 이 도시에서 가장 수익을 많이 낼 수 있는 치킨집의 개수는 최대 M개라는 사실을 알아내었다.

도시에 있는 치킨집 중에서 최대 M개를 고르고, 나머지 치킨집은 모두 폐업시켜야 한다. 어떻게 고르면, 도시의 치킨 거리가 가장 작게 될지 구하는 프로그램을 작성하시오.


생각하기


동작

		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<N; j++) {
				int num = Integer.parseInt(st.nextToken());

				if(num == 2) {
					chickenList.add(new Node(i, j, false));
				}
				else if(num == 1) {
					houseList.add(new Node(i, j, false));
				}
				arr[i][j] = num;
			}
		}

배열arr을 생성하면서, 집의 위치와 치킨 집의 위치의 좌표값을 Node클래스에 담아서 각 list에 저장하면 백트래킹으로 구현이 가능하다.


		// 재귀 탈출 조건
		if(depth == M) {
			int sum = 0;

			for(int i=0; i<hsize; i++) {
				int temp = Integer.MAX_VALUE;

				for(int j=0; j<csize; j++) {

					// 남아있는 치킨집일 경우.
					if(visit[j]) {
                        if(temp == 1) break;
						int dist = Math.abs(houseList.get(i).x - chickenList.get(j).x) + Math.abs(houseList.get(i).y - chickenList.get(j).y);                                 
						temp = Math.min(temp,  dist);
					}
				}
				sum += temp;
			}

			result = Math.min(result, sum);
			return;
		}

재귀 탈출 조건은 depthM과 같을 때 검사에 들어간다.

각 집의 좌표값을 기준으로 현재 열려있는 치킨집 즉, visit이 true인 인덱스에 해당하는 chickenList의 좌표값을 기준으로 거리를 계산해서 최소값으로 갱신하면서, 전체 합을 계산하고,

sumresult을 비교해서 최소값이 선택되면 마지막에 result를 출력하면 결과를 얻을 수 있다.



코드



Java

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

public class Main {
	static int N, M;
	static int result = Integer.MAX_VALUE;

	static int arr[][];
	static boolean visit[];
	static List<Node> houseList = new ArrayList<>();
	static List<Node> chickenList = new ArrayList<>();
	static int csize;
	static int hsize;

	static class Node {
		int x;
		int y;

		public Node(int x, int y, boolean bol) {
			this.x = x;
			this.y = y;
		}
	}

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

		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		arr = new int[N][N];

		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<N; j++) {
				int num = Integer.parseInt(st.nextToken());

				if(num == 2) {
					chickenList.add(new Node(i, j, false));
				}
				else if(num == 1) {
					houseList.add(new Node(i, j, false));
				}
				arr[i][j] = num;
			}
		}

		csize = chickenList.size();
		hsize = houseList.size();

		// 치킨집의 개수만큼 방문여부를 확인하는 배열을 생성함
		visit = new boolean[csize];
		DFS(0, 0);

		System.out.println(result);
	} // End of main

	static void DFS(int index, int depth) {

		// 재귀 탈출 조건
		if(depth == M) {
			int sum = 0;

			for(int i=0; i<hsize; i++) {
				int temp = Integer.MAX_VALUE;

				for(int j=0; j<csize; j++) {

					// 남아있는 치킨집일 경우.
					if(visit[j]) {
                        if(temp == 1) break;
						int dist = Math.abs(houseList.get(i).x - chickenList.get(j).x) + Math.abs(houseList.get(i).y - chickenList.get(j).y);                                 
						temp = Math.min(temp,  dist);
					}
				}
				sum += temp;
			}

			result = Math.min(result, sum);
			return;
		}

		for(int i=index; i<csize; i++) {
			visit[i] = true;
			DFS(i+1, depth+1);
			visit[i] = false;
		}

	} // End of DFS	
} // End of Main class

Kotlin

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

private var N = 0; private var M = 0;
private var csize = 0; private var hsize = 0;
private var result = Integer.MAX_VALUE;

private lateinit var arr : Array<Array<Int>>
private lateinit var visit : Array<Boolean>
private var chickenList : MutableList<Node> = ArrayList<Node>();
private var houseList : MutableList<Node> = ArrayList<Node>();

private class Node(var x : Int, var y : Int)

fun main() {
    val br = BufferedReader( InputStreamReader(System.`in`) )
    var st : StringTokenizer;

    st = StringTokenizer(br.readLine());
    N = st.nextToken().toInt()
    M = st.nextToken().toInt()

    arr = Array(N){Array(N) {0}}
    for(i in 0 until N) {
        st = StringTokenizer(br.readLine())
        for(j in 0 until N) {
            arr[i][j] = st.nextToken().toInt()

            if(arr[i][j] == 1) {
                houseList.add(Node(i, j));
            }
            else if(arr[i][j] == 2) {
                chickenList.add(Node(i, j));
            }
        }
    }

    csize = chickenList.size;
    hsize = houseList.size;
    visit = Array(csize, {false})

    DFS(0, 0)
    print(result)
} // End of main

private fun DFS(index : Int, depth : Int) {

    if (depth == M) {
        var sum = 0;

        for(i in 0 until hsize) {
            var temp = Integer.MAX_VALUE;

            for(j in 0 until csize) {
                if(visit[j]) {
                    if(temp == 1) break;

                    var dist = Math.abs(houseList.get(i).x - chickenList.get(j).x) + Math.abs(houseList.get(i).y - chickenList.get(j).y)
                    temp = Math.min(temp, dist)
                }
            }
            sum += temp;
        }

        result = Math.min(result, sum)
        return;
    }

    for(i in index until csize) {
        visit[i] = true;
        DFS(i+1, depth+1)
        visit[i] = false;
    }

} // End of DFS

0개의 댓글