(BOJ) 치킨배달_15686번

문제 자체가 어려운 것은 아니었지만 자잘한 실수가 많아 기록하게 되었다.

문제

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
이 부분을 지우게 되었다.