글 읽기 - (자바) 다른 풀이법?

zpgy77 5년 전 0

안녕하세요.

일단 문제는 맞추었지만 다른 방법이 궁금하여 질문드립니다.

완전탐색(DFS,BFS)에 익숙치 않아 혹 이를 이용해서 푸신 분이 있으시다면 방법을 여쭤보려 합니다.

제가 푼 방법은 다음과 같습니다.

치킨집과 집의 좌표를 가지는 arraylist를 만듭니다.

2. 치킨집의 모든 combination의 수를 만듭니다.

3. 모든 combination에 따른 치킨거리를 구하여 최소값을 리턴합니다.

다른 풀이가 있다면 어떤 방법이 있을까요?

다음은 제 코드입니다.

import java.util.*;

public class Main {
	static ArrayList<Position> chickens;
	static ArrayList<int[]> cases;
	static ArrayList<Position> homes;
	static int M;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		M = sc.nextInt();
		
		homes = new ArrayList<>();
		cases = new ArrayList<>();
		chickens = new ArrayList<>();
		
		int cur = 0;
		//initialization
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				cur = sc.nextInt();
				if (cur == 1) homes.add(new Position(i,j));
				else if (cur == 2) chickens.add(new Position(i,j));
			}
		}
		int[] data = new int[M];
		
		//genarate permutation
		generateAllcases(chickens, chickens.size(), M, 0, data,0);

		//calculate chicken metric
		int minDistance = Integer.MAX_VALUE;
		for (int i = 0; i < cases.size(); i++) {
			int distance = calculateMetric(i);
			if (minDistance > distance) {
				minDistance = distance;
			}
		}
		System.out.println(minDistance);
	}
	
	private static int calculateMetric(int index) {
		int distance = 0;
		for (int i = 0; i < homes.size(); i++) {
			int min = Integer.MAX_VALUE;
			for (int j = 0; j < cases.get(index).length; j++) {
				int dis = Math.abs(homes.get(i).x - chickens.get(cases.get(index)[j]).x) + Math.abs(homes.get(i).y 
						- chickens.get(cases.get(index)[j]).y);
				if (min > dis) min = dis;
			}
			distance += min;
		}
		return distance;
		
	}

	private static void generateAllcases(ArrayList chicks, int n, int r, int index, int data[], int i) {
		
		if (index == r) {
			
			cases.add(data.clone());
			return;
		}
		
		if (i >= n) return;
		
		data[index] = i;
		generateAllcases(chicks,n,r,index+1,data,i+1);
		generateAllcases(chicks,n,r,index,data,i+1);
	}
	
	
	
	private static class Position{
		int x,y;
		Position(int x, int y){
			this.x = x;
			this.y = y;
		}
	}

}

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

문제

문제

출처

ICPC

(자바) 다른 풀이법?

zpgy77 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말