[백준(Baekjoon)][자바(java)] [삼성 SW 역량 테스트 기출 문제] 15686 : 치킨 배달

 

www.acmicpc.net/problem/15686

15686번: 치킨 배달

 

문제 풀이

 

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

public class Main {
	
	static class Coord {  // coordinate
		int x, y;
		public Coord( int x, int y ) {
			this.x = x;
			this.y = y;
		}
	}
	
	static int n, m, c[][], r, tdm;  // city arr, num of restaurant, min total chicken distance of city
	static List<Coord> hls, rls;  // home/restaurant list
	static int[] dx = { 0, 1, 0, -1 }, dy = { 1, 0, -1, 0 };
	
	/* get a combination of restaurants to open( not to close ) */
	public static void com( int k, int s, int m, int a[], boolean v[] ) {
		int i;
		if( k == m ) {
			/* check restaurants to open */
			boolean o[] = new boolean[r];  // open ?
			for( i = 0; i < m; ++i )
				o[a[i]] = true;
			/* get (total chicken) distance (of city) */
			int td = 0, d, dm, hx, hy, rx, ry; Coord rco;  // total distence, distance, min distance
			for( Coord hco : hls ) {
				dm = Integer.MAX_VALUE;
				hx = hco.x; hy = hco.y;
				for( i = 0; i < r; ++i ) {
					if( o[i] ) {
						rco = rls.get( i );
						rx = rco.x; ry = rco.y;
						d = Math.abs( hx - rx ) + Math.abs( hy - ry );
						dm = dm > d ? d : dm;
					}
				}
				td += dm;
			}
			/* get min (total chicken) distance (of city) */
			tdm = tdm > td ? td : tdm;
			return;
		}
		for( i = s; i < r; ++i ) {
			if( !v[i] ) {
				v[i] = true;
				a[k] = i;
				com( k+1, i+1, m, a, v );
				v[i] = false;
			}
		}
	}

	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() );
		c = new int[n+1][n+1];
		hls = new ArrayList<>();
		rls = new ArrayList<>();
		tdm = Integer.MAX_VALUE;
		int i, j, t;
		for( i = 1; i <= n; ++i ) {
			st = new StringTokenizer( br.readLine() );
			for( j = 1; j <= n; ++j ) {
				t = Integer.parseInt( st.nextToken() );
				c[i][j] = t;
				if( t == 1 )  hls.add( new Coord( i, j ) );
				if( t == 2 )  rls.add( new Coord( i, j ) );
			}
		}
		br.close();
		
		r = rls.size();
		for( i = 1; i <= m; ++i )
			com( 0, 0, i, new int[r], new boolean[r] );
		
		System.out.println( tdm );
	}
}

 

*  x, y 좌표 값으로 구성된 Coord 클래스 생성
*  집들의 위치와 치킨집들의 위치를 담을 각각의 리스트( List<Coord> hls, rls : home/restaurant list ) 생성
*  n x n 크기의 도시 정보 배열( int c[][] : city arr )을 생성하여 값 담음
( 값이 1(집)이면 hls에, 2(치킨집)면 rls에 추가 )
*  치킨집의 개수( r = rls.size() )를 구하고, 이 중 폐업시키지 않을( 계속 운영할 ) 치킨집을 최대 m개 골라야 하므로, 1~m개 뽑는 조합( com() )을 구함
*  계속 운영할 치킨집을 체크하고( boolean o[] : open ), 그 치킨집들만 도시의 치킨 거리( td )를 구함
*  그 중 도시의 치킨 거리의 최솟값( tdm )을 구함