https://www.acmicpc.net/problem/15686
15686번: 치킨 배달
크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸
www.acmicpc.net
문제
DFS + 구현 문제이다. 처음 시간 초과나서 방법을 좀 바꿔서 다시 풀었다.
해결 방안
처음에는 전체 집List, 전체 치킨집List와 visited 배열을 사용하여 전체 치킨집 중 M개를 DFS 와 백트래킹을 이용하여 구현하였다.
하지만 거리를 구하는 과정에서 전체 집에서 전체 치킨집을 돌면서 M개에 포함되지 않는 경우도 조건을 통해 거르다 보니 시간 초과가 났다.
그래서 다음에는 visited 배열을 빼고 선택된 치킨집List를 만들어 M개 만큼 선택된 치킨집 List를 만들어서 거리를 구하였더니 맞출 수 있었다.
나머지 부분은 크게 어렵지 않은 부분이여서 생략한다.
코드 (시간 초과)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
// 치킨 배달
// NxN 도시
// 1x1 칸 (0:빈칸, 1:집, 2:치킨집)
// (r, c) r,c는 1부터 시작
// 치킨 거리 : 집과 가장 가까운 치킨집 사이의 거리
// 도시의 치킨 커리는 모든 집의 치킨 거리의 합
// 치킨집 갯수 M개
// M개 이외 치킨집 폐업, 도시의 치킨 거리가 가장 작게 될지 구하는 프로그램
public class Main {
static int N; // 도시 크기 NxN(2~50)
static int M; // 최대 치킨집 갯수(1~13)
static int[][] map;
static List<int[]> hList = new ArrayList<>(); // 전체 집 위치
static List<int[]> cList = new ArrayList<>(); // 전체 치킨 집 위치
static boolean[] visited;
static int min = Integer.MAX_VALUE; // 가장 작은 도시의 치킨 거리
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str;
str = br.readLine();
N = Integer.parseInt(str.split(" ")[0]);
M = Integer.parseInt(str.split(" ")[1]);
map = new int[N+1][N+1];
StringTokenizer st;
for(int i=1; i<N+1; i++) {
str = br.readLine();
st = new StringTokenizer(str, " ");
for(int j=1; j<N+1; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
// 집 리스트
if(map[i][j] == 1) {
hList.add(new int[] {i, j});
}
// 치킨집 리스트
else if(map[i][j] == 2) {
cList.add(new int[] {i, j});
}
}
}
visited = new boolean[cList.size()];
// ==== 입력 끝 =====
dfs(0);
System.out.println(min);
}
// 치킨집이 M만큼 있는 경우의 치킨 거리 탐색
static void dfs(int depth) {
// 치킨 집이 M만큼 있는 경우
if(depth >= M) {
int distanceSum = 0;
int minDistance;
int distance;
// 각 집에서 M에 포함되는 치킨집들 중 가장 짧은 치킨 거리구하기
for(int i=0; i<hList.size(); i++) {
minDistance = Integer.MAX_VALUE;
distance = 0;
for(int j=0; j<cList.size(); j++) {
// M에 포함된 치킨집
if(visited[j]) {
distance = Math.abs(hList.get(i)[0]-cList.get(j)[0]) + Math.abs(hList.get(i)[1]-cList.get(j)[1]);
minDistance = Math.min(distance, minDistance);
}
}
distanceSum += minDistance;
}
// 가장 작은 도시의 치킨 거리 구하기
min = Math.min(min, distanceSum);
}
else {
// M과 치킨집 갯수가 같으면 폐업되는 치킨 집 없음
if(M == cList.size()) {
for(int i=0; i<cList.size(); i++) {
visited[i] = true;
}
dfs(M);
}
// list에서 치킨집 M만큼 고르기
else {
for(int i=0; i<cList.size(); i++) {
if(!visited[i]) {
visited[i] = true;
dfs(depth+1);
visited[i] = false;
}
}
}
}
}
}
코드 (합격)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
// 치킨 배달
// NxN 도시
// 1x1 칸 (0:빈칸, 1:집, 2:치킨집)
// (r, c) r,c는 1부터 시작
// 치킨 거리 : 집과 가장 가까운 치킨집 사이의 거리
// 도시의 치킨 커리는 모든 집의 치킨 거리의 합
// 치킨집 갯수 M개
// M개 이외 치킨집 폐업, 도시의 치킨 거리가 가장 작게 될지 구하는 프로그램
public class Main {
static int N; // 도시 크기 NxN(2~50)
static int M; // 최대 치킨집 갯수(1~13)
static int[][] map;
static List<int[]> hList = new ArrayList<>(); // 전체 집 위치
static List<int[]> cList = new ArrayList<>(); // 전체 치킨 집 위치
static List<int[]> selected = new ArrayList<>(); // 선택된 치킨집
static int min = Integer.MAX_VALUE; // 가장 작은 도시의 치킨 거리
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str;
str = br.readLine();
N = Integer.parseInt(str.split(" ")[0]);
M = Integer.parseInt(str.split(" ")[1]);
map = new int[N+1][N+1];
StringTokenizer st;
for(int i=1; i<N+1; i++) {
str = br.readLine();
st = new StringTokenizer(str, " ");
for(int j=1; j<N+1; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
// 집 리스트
if(map[i][j] == 1) {
hList.add(new int[] {i, j});
}
// 치킨집 리스트
else if(map[i][j] == 2) {
cList.add(new int[] {i, j});
}
}
}
// ==== 입력 끝 =====
dfs(0,0);
System.out.println(min);
}
// 치킨집이 M만큼 있는 경우의 치킨 거리 탐색
static void dfs(int idx, int depth) {
// 치킨 집을 M만큼 고른 경우
if(depth >= M) {
int distanceSum = 0;
int minDistance;
int distance;
// 각 집에서 M에 포함되는 치킨집들 중 가장 짧은 치킨 거리구하기
for(int i=0; i<hList.size(); i++) {
minDistance = Integer.MAX_VALUE;
distance = 0;
for(int j=0; j<selected.size(); j++) {
// M에 포함된 치킨집
distance = Math.abs(hList.get(i)[0]-selected.get(j)[0]) + Math.abs(hList.get(i)[1]-selected.get(j)[1]);
minDistance = Math.min(distance, minDistance);
}
distanceSum += minDistance;
}
// 가장 작은 도시의 치킨 거리 구하기
min = Math.min(min, distanceSum);
}
else {
// list에서 치킨집 M만큼 고르기
for(int i=idx; i<cList.size(); i++) {
selected.add(cList.get(i));
dfs(i+1, depth+1);
selected.remove(depth);
}
}
}
}
'Old > Algorithms' 카테고리의 다른 글
| [JAVA] 프로그래머스 : JadenCase 문자열 만들기 (Level 2) (0) | 2020.08.28 |
|---|---|
| [JAVA] 프로그래머스 : 124 나라의 숫자 (0) | 2020.08.26 |
| [JAVA] 백준 15685번 : 드래곤 커브(삼성 SW 역량 테스트 기출 문제) (0) | 2020.08.25 |
| [JAVA] 백준 15683번 : 감시(삼성 SW 역량 테스트 기출 문제) (0) | 2020.08.23 |
| [JAVA] 백준 14891번 : 톱니바퀴 (삼성 SW 역량 테스트 기출 문제) (0) | 2020.08.22 |
