[JAVA] 백준 15686번 치킨 배달

[HAVE TO DO]

STUDYING : JAVA

---

문제링크 : https://www.acmicpc.net/problem/15686

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
	
	//집과 치킨집의 최장거리는 2(N-1)
	static int N, M, count = 0, result = 987654321;
	static int[][] map;
	static List<Point> house = new ArrayList<Point>();
	static List<Point> chicken = new ArrayList<Point>();
	static boolean[] visited; //폐업시키지 않을 치킨집 선정

	//집(x, y)과 치킨집(z, k) 사이의 거리 = |x-z| + |y-k|
	//폐업시키는건 원래있던 치킨집 개수 중에 M개를 선택하고 나머지는 전부 폐업시킴
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());;
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		
		map = new int[N][N];
		
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if(map[i][j] == 1) house.add(new Point(i, j));
				else if(map[i][j] == 2) chicken.add(new Point(i, j)); 
			}
		}
		
		visited = new boolean[chicken.size()];
		
		dfs(0);

		bw.write(String.valueOf(result));
		
		br.close();
		bw.flush();
		bw.close();
	}
	
	static void dfs(int index) {	
		visited[index] = true;
		count++;
		
		//치킨집을 M개 뽑았는가? = 맞다면 치킨거리 계산
		if(count == M) {						
			int temp = 0;
			//최소거리 계산
			for (int i = 0; i < house.size(); i++) {
				int dist = 987654321;
				for (int j = 0; j < chicken.size(); j++) {
					if(visited[j]) {
						//만약 j번째 치킨집이 선택되었다면 집들이랑 거리를 계산함						
						dist = Math.min(dist, Math.abs(house.get(i).x - chicken.get(j).x) + Math.abs(house.get(i).y - chicken.get(j).y));
					}
				}
				temp += dist;
			}
			
			result = Math.min(result, temp);
		}		
		//갈 수 있는 곳을 순회
		for (int i = index + 1; i < chicken.size(); i++) {
			if(!visited[i]) {
					dfs(i);
			}
		}
		//체크아웃
		count--;
		visited[index] = false;
	}
}

class Point{
	int x;
	int y;
	
	public Point(int x, int y) {
		super();
		this.x = x;
		this.y = y;
	}

	@Override
	public String toString() {
		return "[x=" + x + ", y=" + y + "]";
	}
	
}

문제점 : 치킨집을 1개만 남기는 경우 1번째 치킨집만 선택한 후 dfs 빠져나옴

 

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

public class Main {
	
	//집과 치킨집의 최장거리는 2(N-1)
	static int N, M, count = 0, result = 987654321;
	static int[][] map;
	static List<Point> house = new ArrayList<Point>();
	static List<Point> chicken = new ArrayList<Point>();
	static boolean[] visited; //폐업시키지 않을 치킨집 선정

	//집(x, y)과 치킨집(z, k) 사이의 거리 = |x-z| + |y-k|
	//폐업시키는건 원래있던 치킨집 개수 중에 M개를 선택하고 나머지는 전부 폐업시킴
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());;
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		
		map = new int[N][N];
		
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if(map[i][j] == 1) house.add(new Point(i, j));
				else if(map[i][j] == 2) chicken.add(new Point(i, j)); 
			}
		}
		
		visited = new boolean[chicken.size()];
		
		dfs(0);

		bw.write(String.valueOf(result));
		
		br.close();
		bw.flush();
		bw.close();
	}
	
	static void dfs(int index) {	
		visited[index] = true;
		count++;
		//치킨집을 M개 뽑았는가? = 맞다면 치킨거리 계산
		if(count == M) {						
			int temp = 0;
			//최소거리 계산
			for (int i = 0; i < house.size(); i++) {
				int dist = 987654321;
				for (int j = 0; j < chicken.size(); j++) {
					if(visited[j]) {
						//만약 j번째 치킨집이 선택되었다면 집들이랑 거리를 계산함						
						dist = Math.min(dist, Math.abs(house.get(i).x - chicken.get(j).x) + Math.abs(house.get(i).y - chicken.get(j).y));
					}
				}
				temp += dist;
			}
			
			result = Math.min(result, temp);
		}	
		
		for (int i = index + 1; i < chicken.size(); i++) {
				dfs(i);

		}
		
		visited[index] = false;
		count--;
		
		if(M == 1) {
			for (int i = index + 1; i < chicken.size(); i++) {
					dfs(i);
			}
		}		
	}
}

class Point{
	int x;
	int y;
	
	public Point(int x, int y) {
		super();
		this.x = x;
		this.y = y;
	}

	@Override
	public String toString() {
		return "[x=" + x + ", y=" + y + "]";
	}
	
}

치킨집이 초기부터 1개인 경우를 따로 처리했지만 틀렸다고 떴다. 이 경우엔 모든 예시를 넣어서 맞았는데도 틀렸습니다가 떠서 너무 슬펐다ㅠㅠㅠㅠㅠ (얼마나 답답했으면 온라인 컴파일러도 써봤다...)

 

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

public class Main {
	
	//집과 치킨집의 최장거리는 2(N-1)
	static int N, M, result = 987654321;
	static int[][] map;
	static List<Point> house = new ArrayList<Point>();
	static List<Point> chicken = new ArrayList<Point>();
	static boolean[] visited; //폐업시키지 않을 치킨집 선정

	//집(x, y)과 치킨집(z, k) 사이의 거리 = |x-z| + |y-k|
	//폐업시키는건 원래있던 치킨집 개수 중에 M개를 선택하고 나머지는 전부 폐업시킴
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());;
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		map = new int[N][N];
		
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if(map[i][j] == 1) house.add(new Point(i, j));
				else if(map[i][j] == 2) chicken.add(new Point(i, j)); 
			}
		}
		
		visited = new boolean[chicken.size()];
		
		dfs(0, 0);

		bw.write(String.valueOf(result));
		
		br.close();
		bw.flush();
		bw.close();
		
	}
	
	static void dfs(int index, int count) {	
		//치킨집을 M개 뽑았는가? = 맞다면 치킨거리 계산
		if(count == M) {						
			int temp = 0;
			//최소거리 계산
			for (int i = 0; i < house.size(); i++) {
				int dist = 987654321;
				for (int j = 0; j < chicken.size(); j++) {
					if(visited[j]) {
						//만약 j번째 치킨집이 선택되었다면 집들이랑 거리를 계산함						
						dist = Math.min(dist, Math.abs(house.get(i).x - chicken.get(j).x) + Math.abs(house.get(i).y - chicken.get(j).y));
					}
				}
				temp += dist;
			}
			result = Math.min(result, temp);
		}
		
		if(index == chicken.size()) {
			return;
		}
		
		visited[index] = true;
		dfs(index + 1, count + 1);
		visited[index] = false;
		dfs(index + 1, count);
			
	}
}

class Point{
	int x;
	int y;
	
	public Point(int x, int y) {
		super();
		this.x = x;
		this.y = y;
	}

	@Override
	public String toString() {
		return "[x=" + x + ", y=" + y + "]";
	}
	
}

그래서 아예 count를 따로 빼지 않고 치킨집 초기값이 1개가 아닌 경우는 count+1로 처리, 1개인 경우에는 count로 dfs 처리를 해주었다.

 

치킨집과 가정집의 좌표는 Point라는 class를 따로 만들어서 ArrayList에 넣어줬다.