문제 자체가 어려운 것은 아니었지만 자잘한 실수가 많아 기록하게 되었다.
문제
https://www.acmicpc.net/problem/15686
접근
순열 조합 및 BFS로 접근하게 되었다.
순열 조합 : 폐업시킬 치킨집의 경우의 수
BFS : 각 집에서 치킨집까지의 최단 거리를 구할 때
코드
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
public class Main {
static class Node {
int x;
int y;
int turn; // 집에서 가장 가까운 치킨집의 거리를 구할 때 사용
Node (int x, int y){
this.x = x;
this.y = y;
}
Node (int x, int y, int turn) {
this.x = x;
this.y = y;
this.turn = turn;
}
}
static int[][] map;
static List<Node> homes = new ArrayList<>(); // 집이 위치한 좌표
static List<Node> chickens = new ArrayList<>(); // 치킨집이 위치한 좌표
static boolean[] isClosed;
static int answer = Integer.MAX_VALUE;
static int[] dx = {0, 0, -1, 1};
static int[] dy = {-1, 1, 0, 0};
public static void main(String[]args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String[] inputs = br.readLine().split(" ");
int n = Integer.parseInt(inputs[0]);
int m = Integer.parseInt(inputs[1]);
map = new int[n][n];
int chickenCnt = 0;
for (int i = 0; i < n; i++) {
inputs = br.readLine().split(" ");
for (int j = 0; j < n; j++) {
map[i][j] = Integer.parseInt(inputs[j]);
if (map[i][j] == 1) {
homes.add(new Node(j, i));
} else if (map[i][j] == 2) {
chickens.add(new Node(j, i));
chickenCnt++;
}
}
}
isClosed = new boolean[chickenCnt];
chickenCnt = chickenCnt - m; // 폐업할 치킨집 개수
dfs (0, chickenCnt, 0);
bw.write(Integer.toString(answer));
bw.flush();
bw.close();
br.close();
}
static void dfs(int cnt, int chickenCnt, int idx) {
if (cnt == chickenCnt) {
int[][] chickensWithClosed = new int[map.length][map[0].length];
for (int i = 0; i < map.length; i++) {
for (int j = 0; j < map[0].length; j++) {
chickensWithClosed[i][j] = map[i][j];
}
}
for (int i = 0; i < isClosed.length; i++) {
// 치킨집 닫은 경우 (무조건 chickenCnt만큼 폐업이 되어야 한다)
if (isClosed[i]) {
Node node = chickens.get(i);
chickensWithClosed[node.y][node.x] = 0;
}
}
solve(chickensWithClosed);
return;
}
for (int i = idx; i < isClosed.length; i++) {
isClosed[i] = true;
dfs(cnt + 1, chickenCnt, i + 1);
isClosed[i] = false;
}
}
static void solve(int[][] chickensWithClosed) {
int n = chickensWithClosed.length;
int m = chickensWithClosed[0].length;
int distSum = 0;
for (int i = 0; i < homes.size(); i++) {
Node node = homes.get(i);
boolean[][] visited = new boolean[n][m];
Queue<Node> q = new LinkedList<>();
q.add(new Node(node.x, node.y, 0));
visited[node.y][node.x] = true;
while (!q.isEmpty()) {
Node tmp = q.remove();
int x = tmp.x;
int y = tmp.y;
int turn = tmp.turn;
if (chickensWithClosed[y][x] == 2) {
distSum += turn;
break;
}
for (int j = 0; j < 4; j++) {
int nextX = x + dx[j];
int nextY = y + dy[j];
if (0 <= nextX && nextX < m && 0 <= nextY && nextY < n) {
if (!visited[nextY][nextX]) {
q.add(new Node(nextX, nextY, turn + 1));
visited[nextY][nextX] = true;
}
}
}
}
}
if (answer > distSum) {
answer = distSum;
}
}
}
정말 말 그대로 폐업할 치킨집을 0으로 바꿔놓은 후 각 집(1)에 대해서 모두 BFS로 탐색하는 방식으로 풀었다. 하지만 이 과정에서 몇몇 실수가 있었다.
문제 풀면서 저질렀던 실수
1. 순열 구할 때 인덱스
dfs 함수의 맨 밑에 있는 for문에서 발생한 실수였다. 매번 자주 하는 실수인데 오늘따라 잡아내기 유독 오래 걸렸던 것 같다.
for (int i = idx; i < isClosed.length; i++) {
isClosed[i] = true;
dfs(cnt + 1, chickenCnt, i + 1);
isClosed[i] = false;
}for문 내에서는 i가 새로운 기준이 되므로 재귀호출 시 시작 인덱스에 대한 인자로 i + 1을 주어야 한다.
for (int i = idx; i < isClosed.length; i++) {
isClosed[i] = true;
dfs(cnt + 1, chickenCnt, idx + 1);
isClosed[i] = false;
}이렇게 idx + 1로 주면 안된다...
2. 무작정 2차원 배열 깊은 복사
int[] arr1 = {1, 2, 3};
int[] arr2 = arr;Java에서 다음과 같이 복사하게 되면 '얕은 복사'가 이루어져 실질적으로 복사한 의미가 없어진다. 깊은 복사를 하기 위해서는...
int[] arr1 = {1, 2, 3};
int[] arr2 = new int[arr1.length];
for (int i = 0; i < arr1.length; i++) {
arr2[i] = arr1[i];
}이렇게 하나씩 옮겨주거나
int[] arr1 = {1, 2, 3};
int[] arr2 = arr1.clone();clone()을 호출하면 된다.
하지만! 2차원 배열을 위의 방법처럼 막바로 clone()하게 되면 arr[i] 부분은 깊은 복사가 될지라도 arr[i][j] 부분은 깊은 복사가 되지 않는다. 따라서 2차원 배열을 깊은 복사를 하려면 이중 for문을 써서 하나씩 옮겨줘야 한다.
3. 고정관념(?)
문제에서 별 말 없었는데 특정 위치에 집(1)이 있다면 그 방향으로는 못지나갈 것이라고 생각해서 solve() 함수의 조건문을 다음과 같이 썼었다.
if (0 <= nextX && nextX < m && 0 <= nextY && nextY < n) {
if (!visited[nextY][nextX] && chickensWithClosed[nextY][nextX] != 1) {
q.add(new Node(nextX, nextY, turn + 1));
visited[nextY][nextX] = true;
}
}하지만, 예제를 직접 풀어보니 1을 거쳐도 된다는 사실을 알게 되어 chickensWithClosed[nextY][nextX] != 1
이 부분을 지우게 되었다.
Coding Duck