프로그래머스 1829번 java

Programmers 코딩테스트 level 2 - 1829번 카카오프렌즈 컬러링북도움말

java로 작성했습니다.

 

---

생각한 점

1. 코드를 작성할대 2차원 배열을 그린다고하면 좌표처럼 생각해 x변수는 넓이, y변수는 높이를 나타냅니다.

2. bfs를 사용했습니다.

import java.util.*;

class Solution {
    static int max;
    static int ans_num;
    static Queue<Node<Integer>> q;
    static class Node<T> {
        public T x;
        public T y;

        public Node(T y, T x) {
            this.x = x;
            this.y = y;
        }
    }
    

    public int[] solution(int m, int n, int[][] picture) {
        // m : height, n : width
        q = new LinkedList<>();
        max = 0;
        ans_num = 0;
        // copy spics to original size
        int[][] spic = new int[m][n];
        for (int x = 0; x < picture.length; x++) {
            for (int y = 0; y < picture[x].length; y++) {
                spic[x][y] = picture[x][y];
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (spic[i][j] != 0) {
                    bfs(i, j, spic, m, n);
                    ans_num++;
                }
            }
        }

        int[] answer = {ans_num, max};
        return answer;
    }

    // y : height, x : width
    void bfs(int y, int x, int[][] spic, int m, int n) {
        int point_num = 0;
        int now_color = spic[y][x];
        q.offer(new Node<Integer>(y, x));
        spic[y][x] = 0;
        point_num++;
        while (!q.isEmpty()) {
            Node<Integer> now = q.poll();
            if (now.y - 1 > -1 && spic[now.y - 1][now.x] == now_color) {
                q.offer(new Node<Integer>(now.y - 1, now.x));
                spic[now.y-1][now.x] = 0;
                point_num++;
            }
            if (now.x + 1 < n && spic[now.y][now.x + 1] == now_color) {
                q.offer(new Node<Integer>(now.y, now.x + 1));
                spic[now.y][now.x+1] = 0;
                point_num++;
            }
            if (now.y + 1 < m && spic[now.y + 1][now.x] == now_color) {
                q.offer(new Node<Integer>(now.y + 1, now.x));
                spic[now.y+1][now.x] = 0;
                point_num++;
            }
            if (now.x - 1 > -1 && spic[now.y][now.x - 1] == now_color) {
                q.offer(new Node<Integer>(now.y, now.x - 1));
                spic[now.y][now.x-1] = 0;
                point_num++;
            }
        }
        if(max < point_num)
            max = point_num;
    }
}