티스토리 뷰

반응형

https://programmers.co.kr/learn/courses/30/lessons/1829?language=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

import java.util.*;

class Solution {
    public int[] solution(int m, int n, int[][] picture) {
        long[][] newPicture = new long[m][n];
        for (int i = 0; i<m; i++){
            for (int j=0; j<n; j++) {
                newPicture[i][j] = picture[i][j];
            }
        }
        Board board = new Board(m,n,newPicture);
        return board.travel();
    }
    public static class Board {
        private final long[][] picture;
        private final int col;
        private final int row;
        private int maxSize;
        private int count;
        private static final int[] dy = {1,-1,0,0};
        private static final int[] dx = {0,0,1,-1};
        
        public Board(int m, int n, long[][] picture) {
            this.col = m;
            this.row = n;
            this.picture = picture;
            maxSize = 0;
            count = 0;
        }
        
        public int[] travel() {
            for(int i=0; i< col; i++) {
                for(int j=0; j< row; j++) {
                    if (picture[i][j]!=0) {
                        maxSize = Math.max(maxSize,bfs(i,j));
                        count++;
                    }
                }
            }
            int[] answer = {count, maxSize};
            return answer;
        }
        
        private int bfs(int y,int x) {
            int res = 1;
            long pixel = picture[y][x];
            picture[y][x]=0;
            Queue<Point> queue = new LinkedList<>();
            queue.add(new Point(x,y));
            while (!queue.isEmpty()) {
                Point p = queue.poll();
                for(int i=0; i<4; i++) {
                    int fy = p.y + dy[i];
                    int fx = p.x + dx[i];
                    if (checkIsRange(fy,fx) && picture[fy][fx] == pixel) {
                        res++;
                        picture[fy][fx]=0;
                        queue.add(new Point(fx,fy));
                    }
                }
            }
            return res;
        }
        
        private boolean checkIsRange(int y,int x) {
            if ( y>=0 && y<col && x>=0 && x<row) {
                return true;
            }else {
                return false;
            }
        }
    }
    public static class Point implements Comparable<Point> {
        public int x;
        public int y;
        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
        
        public int compareTo(Point p) {
            if (this.x > p.x) {
                return 1;
            }
            else if (this.x == p.x) {
                if(this.y >= p.y) {
                    return 1;
                }
            }
            return -1;
        }
    }
}

 

위에서 다시 picture을 재정의 하는 것을 보실 수가 있는데 그 이유는 

https://programmers.co.kr/questions/13972

의 내용을 참고하여 하였더니 통과한 것을 알 수가 있었다.

 

1. Board

 

bfs

특정 거점의 색과 같은(숫자가 같은) 값들을 너비순회를 통해 갯수를 카운팅한다. 

기본적인 bfs 구조로서 방문한 좌표는 queue에 삽입하고 queue가 없어질때까지 돌아가는 형태로 돌아간다.

 

checkIsRange

x,y 좌표의 값이 테두리 안에 잘 있는지 확인하는 메소드이다.

 

travel

색이 있는 좌표일 때 카운팅을 실시하며 돌 때마다 최댓개수에 대하여 갱신 작업을 하는 메소드이다.

 

 

2. Point

x,y에 대하여 표현하기 위해 만들었다.

 

반응형
반응형
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2024/12   »
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31
글 보관함