백준 16234번 인구 이동 (Java)

문제

---

해결 과정

1. 계산 오류

---

첫 시도에서는 국경선 별로 인구를 계산 하지 않아서 실패했다.

연합한 나라끼리만 계산을 진행해야 하는데, 연합한 모든 나라로 인구를 나누었다.

이렇게 문제를 풀 경우 예제 출력과 같은 답이 나오지만, 실제 이동한 인구를 계산해보면 틀린 결과가 나온다.

특히 예제 5번의 인구 움직임을 잘 살펴봐야 한다.

실패 코드

• for문 내 조건을 4개로 나누어서 진행했다.

private static int movePeople() {
	open = new boolean[n][n];
    int team = 0; // 연합 칸 개수 (true일 때만 ++)
    int population = 0; // 인구 수

    /** 
     * i == n - 1, j == n - 1: break;
     *
     * i >= 0, i < n - 1, j >= 0, j < n - 1: 아래, 오른쪽
     *
     * i == n - 1, j < n - 1: 오른쪽
     *
     * i < n - 1, j == n - 1: 아래
     */

    Loop:
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        // 1번: break
        if (i == n - 1 && j == n - 1) {
          break Loop;

          // 2번: 아래, 오른쪽 확인
        } else if (i >= 0 && i < n - 1 && j >= 0 && j < n - 1) {

          for (int k = 0; k < 2; k++) {
            int now = arr[i][j];
            int next = arr[i + dx[k]][j + dy[k]];

            if (Math.abs(now - next) >= min && Math.abs(now - next) <= max) {
              //이미 now 값이 true면 값 더하지 않음
              if (!open[i][j]) {
                open[i][j] = true;
                team++;
                population += arr[i][j];
              }

              // next 는 false일 때 더함
              if (!open[i + dx[k]][j + dy[k]]) {
                open[i + dx[k]][j + dy[k]] = true;
                team++;
                population += arr[i + dx[k]][j + dy[k]];
              }
            }
          }

          //3번: 오른쪽 확인
        } else if (i == n - 1 && j < n - 1) {

          int now = arr[i][j];
          int next = arr[i + dx[1]][j + dy[1]];

          if (Math.abs(now - next) >= min && Math.abs(now - next) <= max) {

            //이미 now 값이 true면 값 더하지 않음
            if (!open[i][j]) {
              open[i][j] = true;
              team++;
              population += arr[i][j];
            }

            // next 는 false일 때 더함
            if (!open[i + dx[1]][j + dy[1]]) {
              open[i + dx[1]][j + dy[1]] = true;
              team++;
              population += arr[i + dx[1]][j + dy[1]];
            }
          }

          // 4번: 아래 확인
        } else if (i < n - 1 && j == n - 1) {
          int now = arr[i][j];
          int next = arr[i + dx[0]][j + dy[0]];

          if (Math.abs(now - next) >= min && Math.abs(now - next) <= max) {

            //이미 now 값이 true면 값 더하지 않음
            if (!open[i][j]) {
              open[i][j] = true;
              team++;
              population += arr[i][j];
            }

            // next 는 false일 때 더함
            if (!open[i + dx[0]][j + dy[0]]) {
              open[i + dx[0]][j + dy[0]] = true;
              team++;
              population += arr[i + dx[0]][j + dy[0]];
            }
          }
        }
      }
    }

    if (team != 0) {  //국경선이 열렸을 때만 인구 수 조정
      setPeople(population, team);
    }
    return team;
  }

  private static void setPeople(int population, int team) {
    //인구 수 계산
    int newPopulation = population / team;

    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        if (open[i][j]) { //국경선 열린 곳만 바꿔줌
          arr[i][j] = newPopulation;
        }
      }
    }
  }
}

2. 시간 초과

---

국경선 별 인구 계산을 위해 dfs를 사용하도록 했다.

그래프 탐색을 사용하니 예제 5번 인구 움직임이 맞게 동작했다.

하지만, 80%에서 계속해서 시간초과가 발생했다.

조건을 주어 반복문을 빠르게 빠져나가게 하는 등 여러가지를 시도했지만 실패했다.

실패 코드

• dfs 사용

while (true) {
	visited = new boolean[n][n];
    int resultCnt = 0;

    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        if (!visited[i][j]) {
          open = new boolean[n][n];

          team = 1;
          population = 0;
          population += arr[i][j];
          visited[i][j] = true;
          open[i][j] = true;

          dfs(i, j);

          //dfs 결과가 1 아닐 때만 계산
          if (team != 1) {
            resultCnt += team;
            setPeople(population, team);
          } else {
            open[i][j] = false; //다른 곳 못 가면 국경문 닫음
          }
        }
      }
    }

    if (resultCnt == 0) {
      break;
    } else {
      answer++;
    }
  }

  System.out.print(answer);
  br.close();
}

private static void dfs(int x, int y) {
  for (int i = 0; i < 4; i++) {
    int nx = x + dx[i];
    int ny = y + dy[i];

    if (nx >= 0 && nx < n && ny >= 0 && ny < n && !visited[nx][ny]) {
      if (Math.abs(arr[x][y] - arr[nx][ny]) >= min && Math.abs(arr[x][y] - arr[nx][ny]) <= max) {

        visited[nx][ny] = true;

        // next 는 false일 때 더함
        if (!open[nx][ny]) {
          open[nx][ny] = true;
          team++;
          population += arr[nx][ny];
        }

        dfs(nx, ny);
      }
    }
  }
}

private static void setPeople(int population, int team) {
  //인구 수 다시 계산
  int newPopulation = population / team;

  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (open[i][j]) { //국경선 열린 곳만 바꿔줌
        arr[i][j] = newPopulation;
      }
    }
  }
}

3. 성공

---

열린 국경선을 체크하는 변수 타입을 배열에서 ArrayList로 변경하니 성공했다.

ArrayList보다 배열이 더 빠르게 처리한다는 생각에 사로 잡혀서 ArrayList를 사용할 생각을 못했다.

2차원 boolean 배열을 사용해서 map의 모든 곳을 확인하는 것보다 국경선이 열린 곳의 (x,y) 좌표 값을 ArrayList에 저장하고 확인하는 것이 최적화할 수 있는 방법이었다.

최종 코드

• dfs
• booelan[][] -> ArrayList<int[]>로 변경

public class No16234 {

  private static int n;
  private static int min;
  private static int max;
  private static int[][] arr;
  private static boolean[][] visited;               //dfs 방문 처리
  private static ArrayList<int[]> open;            //열린 국경선 위치 저장
  private static final int[] dx = {-1, 1, 0, 0};
  private static final int[] dy = {0, 0, -1, 1};
  private static int team;                        // 연합 칸 개수
  private static int population;                  //인구 수

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    n = Integer.parseInt(st.nextToken());
    min = Integer.parseInt(st.nextToken());
    max = Integer.parseInt(st.nextToken());
    arr = new int[n][n];
    int answer = 0;

    for (int i = 0; i < n; i++) {
      st = new StringTokenizer(br.readLine());
      for (int j = 0; j < n; j++) {
        arr[i][j] = Integer.parseInt(st.nextToken());
      }
    }

    while (true) {
      visited = new boolean[n][n];
      boolean isMove = false;

      for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
          if (!visited[i][j]) {
            open = new ArrayList<>();

            team = 1;
            population = 0;
            population += arr[i][j];
            visited[i][j] = true;
            open.add(new int[]{i, j});

            dfs(i, j);

            //dfs 결과가 1 아닐 때(== 국경선이 열렸을 때)만 계산
            if (team != 1) {
              isMove = true;
              setPeople(population, team);
            }
          }
        }
      }

      if (!isMove) {
        break;
      } else {
        answer++;
      }
    }

    System.out.print(answer);
    br.close();
  }

  private static void dfs(int x, int y) {
    for (int i = 0; i < 4; i++) {
      int nx = x + dx[i];
      int ny = y + dy[i];

      if (nx >= 0 && nx < n && ny >= 0 && ny < n && !visited[nx][ny]) {
        if (Math.abs(arr[x][y] - arr[nx][ny]) >= min && Math.abs(arr[x][y] - arr[nx][ny]) <= max) {

          visited[nx][ny] = true;

          // 방문 안 했을 때만 더함
          if (!open.contains(new int[]{nx, ny})) {
            open.add(new int[]{nx, ny});
            team++;
            population += arr[nx][ny];
            dfs(nx, ny);
          }
        }
      }
    }
  }

  private static void setPeople(int population, int allCnt) {
    //인구 수 계산
    int newPopulation = population / allCnt;

    for (int[] i : open) { //국경선 열린 곳만 바꿔줌
      arr[i[0]][i[1]] = newPopulation;
    }
  }
}

4. 결과

---

결과적으로 다른 사람들의 풀이보다 적은 시간이 걸렸다!