메뉴 닫기

[BOJ] 15686 치킨 배달

15686번: 치킨 배달 (acmicpc.net)

이번 문제는 실제로 코딩을 하는데는 한 30분정도 걸렸다.
하지만 처음에 문제를 잘 이해하지 못해서 이상한 방법을 생각했다가 그게 아님을 깨닫는데 시간이 조금 걸렸다.
그리고 solved.ac 티어 보기를 설정해놨더니, 문제 난이도가 실제로는 그렇게 어렵지 않음에도 어렵다고 생각하게 만드는 부작용이 있어서 문제의 티어 표시를 해제해버렸다.
다음부터는 어떤 문제든 겁먹지 않고 도전해보려고 한다. 이번엔 사실 골드 수준이라길래 조금 어렵겠구나 하고 생각했는데, 진짜 아무것도 아니었다…

문제의 입력은 정사각형 N*N 배열의 크기를 의미하는 N, 존재하는 치킨집중 유지할 치킨집의 수 M 그리고 배열의 좌표에 따른 공간의 유형을 입력으로 준다.
치킨집은 2 일반집은 1, 빈공간은 0 형태로 입력이 주어진다.

문제 풀이 방식은

  1. 입력된 집의 수와 좌표를 저장한다.
    – > ArrayList 사용
  2. 입력된 치킨집의 수와 좌표를 저장한다.
    – > ArrayList 사용
  3. 치킨집 X개중 M개의 치킨집만을 유지하는 치킨집의 조합을 만든다.
    0~ X개의 수(치킨집의 인덱스) 중 M개를 뽑아서 조합을 만듬.
  4. 각각의 집의 좌표를 기준으로 폐업하지 않은 치킨집을 한개씩 방문한다.
    인덱스의 조합을 이용하여 폐업하지 않은 치킨집을 정했다.
  5. 방문하면서 치킨집과의 거리를 계산하여 최솟값을 저장한다.
  6. 치킨 거리는 모든집의 치킨거리의 합 이기 때문에 치킨거리를 누적한다.
  7. 누적한 값이 최소인지 비교하고, 다음 치킨집의 조합으로 넘어가서 반복한다.

이 문제는 처음에 클래스를 직접 만들어서 치킨집 클래스와, 일반집 클래스를 만들어서 풀었다.
그렇게 풀고보니 코드가 너무 길어지긴 했지만, 코드가 이해하기 쉬운것 같다.
클래스의 toString메소드 같은 경우에는 사실 필요가 없지만, 입력이 제대로 들어오는지 출력해서 확인하려고 만들었다.

클래스로 풀이

package com.algo.boj;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class BOJ15686Chicken {
	static class Store{
		int posx;
		int posy;
		int id;
		static int no;
		Store(int i, int j){
			this.posx = i;
			this.posy = j;
			this.id= ++no;
		}
		public int distance(int i, int j){
			return Math.abs(this.posx - i) + Math.abs(this.posy - j);
		}
		@Override
		public String toString() {
			return "C"+id+"("+posx + "," + posy + ")";
		}


	}
	static class House{
		int posx;
		int posy;
		int id;
		static int no;
		House(int i, int j){
			this.posx = i;
			this.posy = j;
			this.id= ++no;
		}
		public int distance(int i, int j){
			return Math.abs(this.posx - i) + Math.abs(this.posy - j);
		}
		@Override
		public String toString() {
			return "H"+id+"("+posx + "," + posy + ")";
		}
	}

	static int N; //N*N  
	private static int M;
	private static List<Store> storeList;
	private static List<House> houseList;
	private static int[] numbers;
	private static int result = Integer.MAX_VALUE;
	private static int sum;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		storeList = new ArrayList<>();
		houseList = new ArrayList<>();
		for (int i = 0; i < N; i++) { //입력하면서 치킨집이면 좌표를 storepos 추가
			String line = br.readLine();
			for (int j = 0, k=0; j < N; j++, k+=2) {
				int temp = line.charAt(k)-'0';
				if(temp==1) {
					House house = new House(i,j);
					houseList.add(house);
				}else if(temp==2) {
					Store store = new Store(i,j);
					storeList.add(store);
				}
			}
		}//입력 for
		numbers = new int[storeList.size()];
		combination(0, 0);
		System.out.println(result);

	}

	private static void combination(int cnt, int start) {
		if(cnt==M) {
			//			System.out.println(Arrays.toString(numbers));
			calcDistance();
			result = Math.min(sum, result); // 치킨거리의 최소값을 업데이트 한다.
			return;
		}
		for(int i = start; i<storeList.size(); i++) {
			numbers[cnt] = i;
			combination(cnt+1, i+1);
		}

	}
	//number의 있는 인덱스를 가지고 for문을 돌려서각 집의 거리를 구한다.
	private static void calcDistance() {
		sum = 0;
		for(int i = 0; i < houseList.size(); i++) {// 각집마다먼저 돌린다 거기서 최소값을 구한다
			//number에 있는집만 방문한다.
			int min = 2*N;
			for(int j = 0 ; j< M; j++) { //numbers[j] 가 인덱스로 들어가서치킨집과의 거리를 계산한다.

				int distance =  storeList.get(numbers[j]).distance(houseList.get(i).posx, houseList.get(i).posy);
				min = Math.min(distance, min); //최소거리를 업데이트 한다.
			}
			sum+= min; 
			//			System.out.println(min);
		}
	}

}

배열에 바로 좌표를 저장해서 풀이

package com.algo.boj;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class BOJ15686ChickenOptimize {

	static int N; //N*N  
	private static int M;
	private static List<int[]> storeList;
	private static List<int[]> houseList;
	private static int[] numbers;
	private static int result = Integer.MAX_VALUE;
	private static int sum;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		storeList = new ArrayList<>();
		houseList = new ArrayList<>();
		for (int i = 0; i < N; i++) { //입력하면서 치킨집이면 좌표를 storepos 추가
			String line = br.readLine();
			for (int j = 0, k=0; j < N; j++, k+=2) {
				int temp = line.charAt(k)-'0';
				if(temp==1) {
					int[] t= {i,j};
					houseList.add(t);
				}else if(temp==2) {
					int[] t= {i,j};
					storeList.add(t);
				}
			}
		}//입력 for
		numbers = new int[storeList.size()]; //치킨집 수만큼 배열 생성
		combination(0, 0);
		System.out.println(result);

	}
	//치킨집 M개를 선택한 조합을 구한다.
	private static void combination(int cnt, int start) {
		if(cnt==M) {
			calcDistance();
			result = Math.min(sum, result); // 치킨거리의 최소값을 업데이트 한다.
			return;
		}
		for(int i = start; i<storeList.size(); i++) {
			numbers[cnt] = i;
			combination(cnt+1, i+1);
		}
	}
	//number의 있는 인덱스를 가지고 for문을 돌려서각 집의 거리를 구한다.
	private static void calcDistance() {
		sum = 0;
		for(int i = 0; i < houseList.size(); i++) {// 각집마다먼저 돌린다 거기서 최소값을 구한다
			int min = 2*N;
			for(int j = 0 ; j< M; j++) { //numbers[j] 가 인덱스로 들어가서치킨집과의 거리를 계산한다.
				int distance =  Math.abs(storeList.get(numbers[j])[0] - houseList.get(i)[0]) +Math.abs(storeList.get(numbers[j])[1]-houseList.get(i)[1]); 
				min = Math.min(distance, min); //최소거리를 업데이트 한다.
			}
			sum+= min; 
		}
	}

}
실행속도에는 차이가 없다. 메모리도 거의 차의 없고, 코드길이는 확 줄었다.

Related Posts

2 Comments

답글 남기기

이메일 주소는 공개되지 않습니다.

%d 블로거가 이것을 좋아합니다: