본문 바로가기

Algorithm/Programmers

[2017 카카오코드 예선][BFS] 카카오프렌즈 컬러링북 - Java

문제 바로가기

 

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

6 4 [[1, 1, 1, 0], [1, 2, 2, 0], [1, 0, 0, 1], [0, 0, 0, 1], [0, 0, 0, 3], [0, 0, 0, 3]] [4, 5]

programmers.co.kr

기본적인 BFS 문제입니다. 그림에 있는 영역의 개수와 그 중 가장 큰 영역의 칸의 개수를 구하면 됩니다.

import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

class Solution {
    static class Dir{
        int y, x;
        Dir(int y, int x){
            this.y = y; this.x = x;
        }
    }

    public static boolean isIn(Dir c, int m, int n) {
        if(0<= c.y && c.y < m && 0<= c.x & c.x < n ) return true;
        else return false;
    }

    public static int bfs(Dir s, int[][] picture, boolean[][] v, int m, int n) {
        int[] dy = {1, -1, 0, 0};
        int[] dx = {0, 0, 1, -1};
        int size = 1;
        Queue<Dir> q = new LinkedList<Dir>();
        q.offer(s);
        v[s.y][s.x] = true;
        while(!q.isEmpty()) {
            Dir cur = q.poll();

            for(int i = 0; i< 4; i++) {
                Dir next = new Dir(cur.y + dy[i], cur.x + dx[i]);
                if(!isIn(next, m, n)) continue;
                if(v[next.y][next.x]) continue;
                if(picture[cur.y][cur.x] != picture[next.y][next.x]) continue;

                v[next.y][next.x] = true;
                q.offer(next);
                size++;
            }
        }
        return size;
    }
    public static int[] solution(int m, int n, int[][] picture) {
        List<Integer> sizeList = new LinkedList<Integer>();
        int[] answer = new int[2];
        boolean [][] visited = new boolean[m][n];

        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(picture[i][j] == 0 || visited[i][j]) continue;
                sizeList.add(bfs(new Dir(i, j), picture, visited, m, n));
            }
        }

        answer[0] = sizeList.size();
        answer[1] = Collections.max(sizeList);
        return answer;
    }
}

프로그래머스는 solution 메소드에 파라미터로 입력이 들어와서 다른 메소드들 파라미터가 좀 지저분합니다..

 

picture 배열을 탐색하면서 원소값이 0이 아니거나 한 번도 방문한 적이 없다면 BFS를 돌려서 인접한 네 방향에 있는 친구중 같은 색깔(숫자)인 친구들을 체크해줍니다. 이 때 가장 큰 영역의 크기도 구해주어야 하기 때문에 BFS를 돌리는 메소드에서 거기서 구한 영역의 크기를 리턴해서 저장해 둡니다.

 

pucture 배열을 다 탐색하면 sizeList에는 영역의 개수만큼 각 영역의 크기가 들어 있습니다.

 

따라서 리턴할 answer 배열에 sizeList의 크기와 sizeList의 원소중 최댓값을 넣어서 리턴해주면 끝입니다.

Collections의 max를 사용하면 바로 최댓값을 구할 수 있답니다.

 

 

 

감사합니다.