[99club/TIL] 7주차 - 월요일 TIL(Today I Learned)

안녕하세요. delay100 입니다!

---

미들러 문제

---

1번. 치킨배달 

https://www.acmicpc.net/problem/15686

 

1-1. 실패코드 - 시간초과

package club99;

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

public class p15686 {
	static int N, M, chickenIdxLength;
	static int[] chickenIdx, selectedChickenIdx, homeListIdx;
	static boolean[] visitedChickenIdx;
	static int[][] list;
	static boolean[][] isVisited;
	static int min = Integer.MAX_VALUE;
	public static void main(String args[]) throws IOException {
		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());
		
		ArrayList<Integer> chickenAl = new ArrayList<Integer>();
		ArrayList<Integer> homeAl = new ArrayList<Integer>();
		
		list = new int[N][N];
		isVisited = new boolean[N][N];
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<N; j++) {
				list[i][j] = Integer.parseInt(st.nextToken());
				if(list[i][j] == 2) {
					chickenAl.add(100*i + j);
				} else if(list[i][j] == 1) {
					homeAl.add(100*i + j);		
				}
			}
		}
		
		int chkAlSize = chickenAl.size();
		chickenIdxLength = chkAlSize;
		chickenIdx = new int[chkAlSize]; 
		visitedChickenIdx = new boolean[chkAlSize];
		for(int i=0; i<chkAlSize; i++) {
			chickenIdx[i] = chickenAl.get(i);
		}
		
		homeListIdx = new int[homeAl.size()];
		for(int i=0; i<homeAl.size(); i++) {
			homeListIdx[i] = homeAl.get(i);
		}
		selectedChickenIdx = new int[M];
		// 백트래킹
		// list에서 M가지 고르는 백트래킹
		func(0, 0); // chickenIdx, 현재까지 정해진 0~M의 개수 
		
		bw.write(Integer.toString(min));
		br.close();
		bw.close();
	}
	
	/**
	 * chickenIdx 리스트에서 M개만큼 조합하는 메소드(경우의 수 구하기)
	 * @param chickenIdx에서 현재 고를 index
	 * @param cnt 현재까지 선택된 치킨집의 개수
	 */
	private static void func(int idx, int cnt) {
		if(cnt==M) {
			min = Math.min(min, solve());
			return;
		}
		
		for(int i=idx; i<chickenIdxLength; i++) {
			if(visitedChickenIdx[i]) continue;
			visitedChickenIdx[i] = true;
			selectedChickenIdx[cnt] = chickenIdx[i];
			func(idx+1, cnt+1);
			visitedChickenIdx[i] = false;
		}
	}
	
	/**
	 * 백트래킹의 종료 시점에 호출되는 메소드
	 */
	private static int solve() {
		int sum = 0;
		int homeListLength = homeListIdx.length;
		// bfs 호출
		for(int i=0; i<homeListLength; i++) {
			int temp = Integer.MAX_VALUE;
			for(int k=0; k<M; k++) {
	
				int x1 = selectedChickenIdx[k]/100;
				int y1 = selectedChickenIdx[k]%100;

				int x2 = homeListIdx[i]/100;
				int y2 = homeListIdx[i]%100;
				
				int len = Math.abs(x1-x2) + Math.abs(y1-y2);
				temp = Integer.min(temp, len);
			}
			sum += temp;
		}
		return sum;
	}
}

 

1-2. 성공코드

계속 현재 idx에 값을 호출해서 시간초과가 날 수 밖에 없는 코드였습니다..

// 문제가 된 재귀호출
func(idx+1, cnt+1);

// 변경 후 재귀호출
func(i+1, cnt+1);

 

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

public class Main {
	static int N, M, chkAlSize, homeAlSize;
	static ArrayList<Integer> chickenAl, homeAl;
	static boolean[] visitedChickenIdx;
	static int[][] list;
	static int min = Integer.MAX_VALUE;
	public static void main(String args[]) throws IOException {
		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());
		
		chickenAl = new ArrayList<Integer>();
		homeAl = new ArrayList<Integer>();
		list = new int[N][N];
		
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<N; j++) {
				list[i][j] = Integer.parseInt(st.nextToken());
				if(list[i][j] == 2) {
					chickenAl.add(100*i + j);
				} else if(list[i][j] == 1) {
					homeAl.add(100*i + j);		
				}
			}
		}
		
		chkAlSize = chickenAl.size();
		homeAlSize = homeAl.size();
		visitedChickenIdx = new boolean[chkAlSize];
		// 백트래킹
		// list에서 M가지 고르는 백트래킹
		func(0, 0); // chickenIdx, 현재까지 정해진 0~M의 개수 
		
		bw.write(Integer.toString(min));
		br.close();
		bw.close();
	}
	
	/**
	 * chickenIdx 리스트에서 M개만큼 조합하는 메소드(경우의 수 구하기)
	 * @param chickenIdx에서 현재 고를 index
	 * @param cnt 현재까지 선택된 치킨집의 개수
	 */
	private static void func(int idx, int cnt) {
		if(cnt==M) {
			min = Math.min(min, solve());
			return;
		}
		
		for(int i=idx; i<chkAlSize; i++) {
			if(visitedChickenIdx[i]) continue;
			visitedChickenIdx[i] = true;
			func(i+1, cnt+1);
			visitedChickenIdx[i] = false;
		}
	}
	
	/**
	 * 각 집(1)별로 최소값 구하기
	 */
	private static int solve() {
		int sum = 0;
		for(int i=0; i<homeAlSize; i++) {
			int temp = Integer.MAX_VALUE;
			for(int k=0; k<chkAlSize; k++) {
				if(visitedChickenIdx[k]) {
					int x1 = chickenAl.get(k)/100;
					int y1 = chickenAl.get(k)%100;
	
					int x2 = homeAl.get(i)/100;
					int y2 = homeAl.get(i)%100;
					
					int len = Math.abs(x1-x2) + Math.abs(y1-y2);
					temp = Math.min(temp, len);
				}
			}
			sum += temp;
		}
		return sum;
	}
}

---

+ 비기너 문제

사분면 고르기 https://www.acmicpc.net/problem/14681

+ 챌린저 문제

동전 0 https://www.acmicpc.net/problem/11047

---

봐주셔서 감사합니다. 피드백 환영합니다.