문제링크
문제풀이
DFS방법과 BFS방법을 섞어서 접근했다. M개의 치킨집을 고르는 과정은 DFS로 구현했고
DFS로 고른 치킨집들을 토대로 BFS를 돌려서 최소의 치킨 거리를 구할수 있도록 접근했다.
백준의 연구소3과 굉장히 유사하게 풀었다.
map은 bfs를 돌때마다 새롭게 바뀔 변수, originMap은 일반 집들의 위치를 가지고 있을 고정된 형태의 변수이다.
houseList에는 집들의 위치와, 그 집들의 치킨거리를 담을 것이며, chickenList에는 최초의 모든 치킨집들의 위치를 저장하여 dfs 사용할 것이다.map = new int[n][n]; originMap = new int[n][n]; chk = new boolean[n][n]; List<Node> houseList = new ArrayList<>(); List<Node> chickenList = new ArrayList<>();
dfs를 사용해서 중복을 허용하지 않는 조합으로 치킨집들을 선택했다.
public static void dfs(int idx, int num, List<Node> houseList, List<Node> chickenList, Node[] node) { if (idx == m) { bfs(houseList, node); return; } for (int i = num; i < chickenList.size(); i++) { if (chickenchk[i]) { continue; } node[idx] = chickenList.get(i); chickenchk[i] = true; dfs(idx + 1, i + 1, houseList, chickenList, node); chickenchk[i] = false; } }
치킨 거리를 구하는 과정은
1. 새롭게 선택된 치킨집들을 가지고 새롭게 맵을 만든다.for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { map[i][j] = originMap[i][j]; } } //치킨 집 위 for (int i = 0; i < node.length; i++) { map[node[i].y][node[i].x] = 2; }2.houseList(주거집들의 모음)에서 거리값들을 다시 Integer.MAX_VALUE로 초기화 시킨다.
for(int i=0; i<houseList.size(); i++){ houseList.get(i).distance = Integer.MAX_VALUE; }
- 한 집에 대해서 크게 for문을 돌며, 최초의 위치를 queue에 넣고, chk(방문했는지 체크하는 2차원 배열)을 다시 초기화 시킨다.
for (int p = 0; p < houseList.size(); p++) { queue.add(houseList.get(p)); for(int i=0; i<n; i++){ Arrays.fill(chk[i],false); }
- 그 다음 과정은 bfs 기본 틀과 비슷한데 bfs를 돌경우에 거리가1-> 거리가2 -> 거리가3 과 같은 거리를 모두 탐색한 후에 치킨거리를 탐색한다. 그렇기에 먼저 치킨집 (map의 값이2)을 발견한 경우 그때의 거리를 찾으면 더이상 bfs를 돌지 않아도 된다. 그렇기에
해당집에서 최초의 2를 발견한 경우에 그 값을 그집의 치킨 거리로 설정하고, checker를 true로 바꿔서 while까지 종료시킨다.
이 부분에서 바로 종료를 하지 않았더니 시간초과가 발생했다.while (!queue.isEmpty()) { Node now = queue.poll(); chk[now.y][now.x] = true; for (int i = 0; i < 4; i++) { int now_y = now.y + diry[i]; int now_x = now.x + dirx[i]; if (now_y >= 0 && now_y < n && now_x >= 0 && now_x < n) { if (!chk[now_y][now_x]) { if (map[now_y][now_x] == 2) { houseList.get(p).distance = Math.abs(houseList.get(p).y-now_y) + Math.abs(houseList.get(p).x-now_x); chk[now_y][now_x] = true; checker = true; break; } else { chk[now_y][now_x] = true; queue.add(new Node(now_y, now_x, 0)); } } } } if(checker){ checker = false; queue.clear(); } }
- 마지막으로 각집마다의 치킨거리를 sum에다가 더한후에 res(결과)와 Math.min 연산을 한다.
sum += houseList.get(p).distance; } res = Math.min(res,sum);
코드
import java.util.*;
public class Main {
static int n;
static int m;
static int[][] map;
static int[][] originMap;
static boolean[][] chk;
static boolean[] chickenchk;
static int res = Integer.MAX_VALUE;
static int[] diry = {-1, 0, 1, 0};
static int[] dirx = {0, 1, 0, -1};
static class Node {
int y;
int x;
int distance;
public Node(int y, int x, int distance) {
this.y = y;
this.x = x;
this.distance = distance;
}
public String toString() {
return "y : " + y + " x : " + x + " distance : " + distance;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
map = new int[n][n];
originMap = new int[n][n];
chk = new boolean[n][n];
List<Node> houseList = new ArrayList<>();
List<Node> chickenList = new ArrayList<>();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
map[i][j] = sc.nextInt();
originMap[i][j] = map[i][j];
if (map[i][j] == 1) {
houseList.add(new Node(i, j, Integer.MAX_VALUE));
} else if (map[i][j] == 2) {
chickenList.add(new Node(i, j, 0));
originMap[i][j] = 0;
}
}
}
chickenchk = new boolean[chickenList.size()];
Node[] node = new Node[m];
dfs(0, 0, houseList, chickenList, node);
System.out.println(res);
}
public static void dfs(int idx, int num, List<Node> houseList, List<Node> chickenList, Node[] node) {
if (idx == m) {
bfs(houseList, node);
return;
}
for (int i = num; i < chickenList.size(); i++) {
if (chickenchk[i]) {
continue;
}
node[idx] = chickenList.get(i);
chickenchk[i] = true;
dfs(idx + 1, i + 1, houseList, chickenList, node);
chickenchk[i] = false;
}
}
public static void bfs(List<Node> houseList, Node[] node) {
Queue<Node> queue = new LinkedList<>();
int sum = 0;
boolean checker = false;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
map[i][j] = originMap[i][j];
}
}
//치킨 집 위
for (int i = 0; i < node.length; i++) {
map[node[i].y][node[i].x] = 2;
}
for(int i=0; i<houseList.size(); i++){
houseList.get(i).distance = Integer.MAX_VALUE;
}
for (int p = 0; p < houseList.size(); p++) {
queue.add(houseList.get(p));
for(int i=0; i<n; i++){
Arrays.fill(chk[i],false);
}
while (!queue.isEmpty()) {
Node now = queue.poll();
chk[now.y][now.x] = true;
for (int i = 0; i < 4; i++) {
int now_y = now.y + diry[i];
int now_x = now.x + dirx[i];
if (now_y >= 0 && now_y < n && now_x >= 0 && now_x < n) {
if (!chk[now_y][now_x]) {
if (map[now_y][now_x] == 2) {
houseList.get(p).distance = Math.abs(houseList.get(p).y-now_y) + Math.abs(houseList.get(p).x-now_x);
chk[now_y][now_x] = true;
checker = true;
break;
} else {
chk[now_y][now_x] = true;
queue.add(new Node(now_y, now_x, 0));
}
}
}
}
if(checker){
checker = false;
queue.clear();
}
}
sum += houseList.get(p).distance;
}
res = Math.min(res,sum);
}
}
하루하루는 성실하게 인생 전체는 되는대로