[JAVA] 카카오프렌즈 컬러링북

 

문제

https://programmers.co.kr/learn/courses/30/lessons/1829

코딩테스트 연습 - 카카오프렌즈 컬러링북

내 풀이

import java.util.LinkedList;
import java.util.Queue;

class Solution {
  public static int[][] arrow = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

  public int[] solution(int m, int n, int[][] picture) {
    int[] answer = new int[2];
    int[][] copiedPic = new int[m + 2][n + 2];
    for (int i = 1; i <= m; i++) {
      for (int j = 1; j <= n; j++) {
        copiedPic[i][j] = picture[i - 1][j - 1];
      }
    }
    for (int i = 1; i <= m; i++) {
      for (int j = 1; j <= n; j++) {
        final int color = copiedPic[i][j];
        if (color != 0) {
          answer[0]++;
          answer[1] = Math.max(answer[1], dfs(copiedPic, color, i, j));
        }
      }
    }
    return answer;
  }

  public int dfs(int[][] picture, int color, int row, int col) {
    int count = 0;
    Queue<Coordinate> q = new LinkedList<>();
    q.add(new Coordinate(row, col));
    picture[row][col] = 0;
    while (!q.isEmpty()) {
      count++;
      final Coordinate now = q.poll();
      for (int i = 0; i < 4; i++) {
        int nextRow = now.row + arrow[i][0];
        int nextCol = now.col + arrow[i][1];
        if (picture[nextRow][nextCol] == color) {
          picture[nextRow][nextCol] = 0;
          q.add(new Coordinate(nextRow, nextCol));
        }
      }
    }
    return count;
  }

  class Coordinate {

    public int row;
    public int col;

    Coordinate(int row, int col) {
      this.row = row;
      this.col = col;
    }
  }
}

알게 된 것

1. Queue를 이용한 BFS 구현을 자바버전으로 이젠 맘편히 해낼 수 있게 된 듯 하다.

2. 2d array (여기서는 arrow) 를 선언 및 초기화 시에 중괄호를 이용해 쉽게 만들 수 있다.

public static int[][] arrow = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

3. 배열복사의 훨씬 효율적인 메서드를 발견했다.

System.arraycopy(Object var0, int var1, Object var2, int var3, int var4);
// (소스 객체, 소스 객체 복사의 출발 인덱스, 대상 객체, 대상 객체의 출발 인덱스, 총 길이)

    for (int i = 1; i <= m; i++) {
      if (n >= 0)
        System.arraycopy(picture[i - 1], 0, copiedPic[i], 1, n);
    }

조금 인덱스때문에 헷갈려보이겠지만 그건 IndexBoundException을 막기 위해 피복사배열의 크기를 row + 2, col + 2 하였기 때문이다.

i=1일 때 해석하면, picture[0] 행의 0열부터 모든 값들은 copiedPic[1] 의 1열부터 복사가 되며, 이 때 열의 길이는 n이다.

피드백

inner class 선언 또한 기존의 클래스 정의처럼 그대로 하면 되는 듯 하다.