[알고리즘_풀이] 카카오 예선, 카카오프렌즈 컬러링북

java, bfs로 구현한 코드

 

전형적인 graph응용문제였고 이에 따라 graph에 대하여 전반적으로 공부했다.

 

IDE용 코드

package codingTest;

import java.util.*;

class Node{
    int x;
    int y;
    Node(int x, int y){
        this.x = x;
        this.y = y;
    }
}

public class kakao_coloringbook {
    static boolean[][] marked = null;
    static int[][] pictures = null;
    public static int bfs(int i, int j) {
        //System.out.println(marked[i][j]);
        int tmpPicture = pictures[i][j];
        System.out.println(pictures[i][j] + " " + i + " " + j );
        marked[i][j] = true;
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(i, j));

        int[] dx = {0, 0, 1, -1};
        int[] dy = {1, -1, 0, 0};
        int count = 1;

        while(!q.isEmpty()){
            Node out = q.poll();

            for(int k=0; k<4; k++){
                int x = out.x+dx[k];
                int y = out.y+dy[k];
                if(x>=0 && y>=0 && x<pictures.length && y<pictures[0].length){
                    if(!marked[x][y] && pictures[x][y] == tmpPicture && pictures[i][j] > 0){
                        count++;
                        marked[x][y] = true;
                        q.add(new Node(x, y));
                    }
                }
            }

        }

        return count;
    }


    public static int[] solution(int m, int n, int[][] picture) {
        int numberOfArea = 0;
        int maxSizeOfOneArea = 0;

        marked = new boolean[m][n];
        pictures = new int[m][n];

        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                pictures[i][j] = picture[i][j];
            }
        }

        List<Integer> count = new LinkedList<>();

        //bfs구현
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(!marked[i][j] && pictures[i][j] > 0){
                    marked[i][j] = true;
                    count.add(bfs(i, j));
                }
            }
        }

        Collections.sort(count);
        Collections.reverse(count);

        numberOfArea = count.size();
        maxSizeOfOneArea = count.get(0);

        int[] answer = new int[2];
        answer[0] = numberOfArea;
        answer[1] = maxSizeOfOneArea;
        return answer;
    }

    public static void main(String[] args) {
        int m = 6;
        int n = 4;
        int[][] picture = {{1, 1, 1, 0}, {1, 2, 2, 0}, {1, 0, 0, 1}, {0, 0, 0, 1}, {0, 0, 0, 3}, {0, 0, 0, 3}};
        int[] answer = solution(m, n, picture);

        System.out.println(answer[0] + " " + answer[1]);

    }
}

 

프로그래머스용 코드 

import java.util.*;

class Node{
    int x;
    int y;
    Node(int x, int y){
        this.x = x;
        this.y = y;
    }
}

class Solution {
   static boolean[][] marked = null;
    static int[][] pictures = null;
    public static int bfs(int i, int j) {
        //System.out.println(marked[i][j]);
        int tmpPicture = pictures[i][j];
        System.out.println(pictures[i][j] + " " + i + " " + j );
        marked[i][j] = true;
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(i, j));

        int[] dx = {0, 0, 1, -1};
        int[] dy = {1, -1, 0, 0};
        int count = 1;

        while(!q.isEmpty()){
            Node out = q.poll();

            for(int k=0; k<4; k++){
                int x = out.x+dx[k];
                int y = out.y+dy[k];
                if(x>=0 && y>=0 && x<pictures.length && y<pictures[0].length){
                    if(!marked[x][y] && pictures[x][y] == tmpPicture && pictures[i][j] > 0){
                        count++;
                        marked[x][y] = true;
                        q.add(new Node(x, y));
                    }
                }
            }

        }

        return count;
    }
   public int[] solution(int m, int n, int[][] picture) {
        int numberOfArea = 0;
        int maxSizeOfOneArea = 0;

        marked = new boolean[m][n];
        pictures = new int[m][n];

        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                pictures[i][j] = picture[i][j];
            }
        }

        List<Integer> count = new LinkedList<>();

        //bfs구현
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(!marked[i][j] && pictures[i][j] > 0){
                    marked[i][j] = true;
                    count.add(bfs(i, j));
                }
            }
        }

        System.out.println("count : " + count);
        Collections.sort(count);
        Collections.reverse(count);

        numberOfArea = count.size();
        maxSizeOfOneArea = count.get(0);

        int[] answer = new int[2];
        answer[0] = numberOfArea;
        answer[1] = maxSizeOfOneArea;
        return answer;
    }
}

 

 

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

코딩테스트 연습 - 카카오프렌즈 컬러링북 | 프로그래머스