프로그래머스 Lv.2) 카카오프렌즈 컬러링북

카카오프렌즈 컬러링북

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

풀이

그림의 난이도를 영역의 수로 정의했다. (영역이란 상하좌우로 연결된 같은 색상의 공간을 의미한다.
picture의 원소 중 값이 0인 경우는 색칠하지 않는 영역을 뜻한다.

이 두 부분만 유의하면 어렵지 않게 풀 수 있었다.

영역의 갯수와 가장 넓은 공간을 가지고 있는 영역의 넓이를 리턴해야하기 때문에

1. 먼저 grouping을 해주고

2. 해당 그룹의 넓이를 HashMap에 저장해주었다.

 

grouping을 할때는 out of index 방지와 같은 값을 가지고 있는지만 체크하면 된다.

상하좌우를 검사해서 같은 값을 가진 좌표는 queue에 넣고 queue에서 모두 꺼낼 때 까지 반복을 해주었다.

grouping이 끝나면 HashMap에 그룹 넘버와 넓이를 저장해주고, 모든 grouping이 끝난 후에는 map의 size와 가장 넓은 영역을 리턴했다.

하지만, 지금 드는 생각인데 굳이 HashMap을 쓰지 않고 Max값만 저장해주는게 더 괜찮을 것 같다.

살짝 수정해서 코드 2를 만들어야지 .. ㅎㅎ

 

코드1

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

public class ColoringBook_1829 {
    // 북 동 남 서
    final static int[] dx = {0,1,0,-1};
    final static int[] dy = {-1,0,1,0};
    static HashMap<Integer, Integer> resultMap;

    private static int[] solution(int m, int n, int[][] picture) {
        int[] answer = getAnswer(m,n,new int[m][n],picture);
        return answer;
    }

    private static int[] getAnswer(int m, int n, int[][] visit,int[][] picture) {
        resultMap = new HashMap<>();
        int group =1;

        for(int y=0; y<m; y++) {
            for(int x=0; x<n; x++) {
                if(visit[y][x] ==0 && picture[y][x] !=0) {
                    visit = grouping(visit, picture, x,y,group++);
                }
            }
        }
        int max = 0;
        for(int i=1; i<group; i++) {
            max = Math.max(max, resultMap.get(i));
        }

        return new int[]{resultMap.size(), max};
    }

    private static int[][] grouping(int[][] visit, int[][] picture, int x, int y, int group) {
        int cnt =1;
        visit[y][x] =group;
        Queue<Pos_1829> queue = new LinkedList<>();
        queue.offer(new Pos_1829(x,y));

        while(!queue.isEmpty()) {
            Pos_1829 pos = queue.poll();
            for (int i = 0; i < 4; i++) {
                int nx = pos.x + dx[i];
                int ny = pos.y + dy[i];
                if (isInArea(nx, ny, visit[0].length, visit.length)) {
                    if (isSame(pos.x, pos.y, nx, ny, picture) && visit[ny][nx] == 0) {
                        visit[ny][nx] = group;
                        queue.offer(new Pos_1829(nx,ny));
                        cnt++;
                    }
                }
            }
        }
        resultMap.put(group, cnt);
        return visit;
    }

    private static boolean isSame(int x, int y, int nx, int ny, int[][] picture) {
        return picture[y][x] == picture[ny][nx] ? true : false;
    }

    private static boolean isInArea(int x, int y, int maxX, int maxY) {
        return x>=0 && x<maxX && y >=0 && y<maxY ? true : false;
    }

    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[] result = solution(m,n,picture);
        System.out.println(result[0]);
        System.out.println(result[1]);
    }
}

class Pos_1829 {
    int x;
    int y;

    public Pos_1829(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

 

코드2

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

public class ColoringBook_1829 {
    // 북 동 남 서
    final static int[] dx = {0,1,0,-1};
    final static int[] dy = {-1,0,1,0};
    static int max;

    private static int[] solution(int m, int n, int[][] picture) {
        int[] answer = getAnswer(m,n,new int[m][n],picture);
        return answer;
    }

    private static int[] getAnswer(int m, int n, int[][] visit,int[][] picture) {
        max =0;
        int group =1;

        for(int y=0; y<m; y++) {
            for(int x=0; x<n; x++) {
                if(visit[y][x] ==0 && picture[y][x] !=0) {
                    visit = grouping(visit, picture, x,y,group++);
                }
            }
        }
        return new int[]{group-1, max};
    }

    private static int[][] grouping(int[][] visit, int[][] picture, int x, int y, int group) {
        int cnt =1;
        visit[y][x] =group;
        Queue<Pos_1829> queue = new LinkedList<>();
        queue.offer(new Pos_1829(x,y));

        while(!queue.isEmpty()) {
            Pos_1829 pos = queue.poll();
            for (int i = 0; i < 4; i++) {
                int nx = pos.x + dx[i];
                int ny = pos.y + dy[i];
                if (isInArea(nx, ny, visit[0].length, visit.length)) {
                    if (isSame(pos.x, pos.y, nx, ny, picture) && visit[ny][nx] == 0) {
                        visit[ny][nx] = group;
                        queue.offer(new Pos_1829(nx,ny));
                        cnt++;
                    }
                }
            }
        }
        max = Math.max(cnt,max);
        return visit;
    }

    private static boolean isSame(int x, int y, int nx, int ny, int[][] picture) {
        return picture[y][x] == picture[ny][nx] ? true : false;
    }

    private static boolean isInArea(int x, int y, int maxX, int maxY) {
        return x>=0 && x<maxX && y >=0 && y<maxY ? true : false;
    }

    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[] result = solution(m,n,picture);
        System.out.println(result[0]);
        System.out.println(result[1]);
    }
}

class Pos_1829 {
    int x;
    int y;

    public Pos_1829(int x, int y) {
        this.x = x;
        this.y = y;
    }
}