[삼성 SW Expert Academy] 음식배달 10888 [JAVA]

Problem

※ SW Expert Academy는 문제의 무단 복제를 금지하고 있기 때문에, 기재하지 못한 점 양해 부탁드립니다.

Link

※ 하단의 Link를 클릭해도, 로그인 후 열람이 가능합니다.

swexpertacademy.com/main/code/userProblem/userProblemDetail.do?contestProbId=AXUqw9zKYaoDFASe&categoryId=AXUqw9zKYaoDFASe&categoryType=CODE

SW Expert Academy

풀이방법

1. 예전에 풀었던 백준의 치킨배달과 비슷한 문제였다. - 어쩌면 같은,
 - 참고 주소 : 2020/10/07 - [알고리즘] - [백준] 치킨 배달 15686 [JAVA]

2. 사고의 흐름은 
 1) 상가(음식배달집)를 세울 수 있는 부분 조합 경우의 수 뽑기 
 2) 각 상가에서 가장 가까운 '집' 의 거리를 구한다.
   - 다익스트라 알고리즘 처럼, 각 '집'에서의 최소거리를 배열로 만들어서 갱신함으로써 해결했다.
 3) 각 집의 거리를 모두 더해준다. 

힘들었던 점

1. if문 안에서 Totaldist를 더해줬어야 했는데, 반복문 밖에서 처리하는 사소한 실수는 생각보다 시간을 많이 뺏었다. ㅠ

참고할 점

1. 과거, 치킨 배달 문제는 좀 더 효율적으로 풀었는데 오랜만에 풀다보니, 쉽지 않았다. 복습 많이하자..

코드

package 알고리즘공부하기;

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

public class 음식배달_sw10888 {

	static int N, Tc, storecnt, homecnt;
	static int[][] map;
	static ArrayList<Point> home, store;
	static int answer = Integer.MAX_VALUE;
	static boolean[] visited;

	public static class Point {
		int r;
		int c;

		public Point(int r, int c) {
			this.r = r;
			this.c = c;
		}
	}

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		StringTokenizer st;
		Tc = sc.nextInt();

		for (int tc = 1; tc <= Tc; tc++) {

			N = sc.nextInt();

			// initial
			map = new int[N][N];
			answer = Integer.MAX_VALUE;
			home = new ArrayList<>();
			store = new ArrayList<>();
			storecnt = 0;
			homecnt = 0;
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					map[i][j] = sc.nextInt();

					/*
					 * 0 : 빈 곳 1 : 집 2 이상 : 상가
					 */
					if (map[i][j] == 1) {
						home.add(new Point(i, j));
						homecnt++;
					} else if (map[i][j] >= 2) {
						store.add(new Point(i, j));
						storecnt++;

					}
				}
			}

			// 1. 배달 음식집의 위치를 통해 부분조합의 경우를 모두 뽑자.
			visited = new boolean[storecnt];
			perm(0);
			// 2. 각 종류에 따라서 모든 집과의 배달 거리와 운용비를 구하고			
			// 3. 그 중 최소값을 출력하자.


			System.out.println("#" + tc + " " + answer);
		}

	}
	private static void getFoodDist(int idx, int [] homedist) {
		
		// 모든 집 방문하면서 해당 상가와의 최소 거리를 저장?
		// 해당 상가는?
		Point cur = store.get(idx);
		
		for ( int i=0; i<homecnt; i++) {
			
			int dist = Math.abs(cur.r - home.get(i).r ) + Math.abs(cur.c- home.get(i).c);
			// 해당 집과의 거리가 더 짧으면 최소 거리 갱신
			if ( homedist[i] > dist ) {
				homedist[i] = dist;
				
			}
		}
	}
	private static void perm(int idx) {
		int selcnt =0;
		
		// 기저 조건
		if (idx == storecnt) {
			int Totaldist = 0;
			int dist =0;
			int[] homedist = new int[homecnt];
			Arrays.fill(homedist, Integer.MAX_VALUE);
			for ( int i=0; i<storecnt; i++) {
				// 선택된 상가에 대해서
				if( visited[i]) {
					
					selcnt ++;
					// 해당 상가와, 집 간의 거리를 구해보자.
					getFoodDist(i, homedist);
					// 운용비
					dist = map[ store.get(i).r][ store.get(i).c] ;
					
					Totaldist += dist ;
				}
			}
			if ( selcnt == 0 ) return;
			// 갱신된 각 집에서의 최소거리 더하기 
			for( int i=0; i<homecnt ; i++) {
				Totaldist += homedist[i];
			}
			
			if ( Totaldist < answer ) {
				answer = Totaldist;
			}
			
			return;
		}

		// 조합 구하자.
		visited[idx] = true;
		perm(idx + 1);
		visited[idx] = false;
		perm(idx + 1);
	}
}