[프로그래머스]카카오 프렌즈 컬러링북 (java)

문제 설명

전형적인 BFS문제이다.

설명한다면 이 문제에 대해 말하기 보단 BFS에 대해 말하므로 설명은 생략.

접근

문제를 이해하는 건 쉽다. 하지만 전에 이런 종류의 문제를 비효율적으로 구현한 적이 있어 효율적으로 탐색하는 방법에 대해 적으려 한다.

문제의 상황은 다음과 같다.

점들을 bfs로 탐색해야 하는데, 모든 위치를 방문해야 한다.

초기 접근

1. visited 모든 배열을 탐색한다.
2. 미방문 했다면 그 부분 기준으로 BFS 탐색
3. 다시 visited 모든 배열을 탐색한다.
4. 미방문 한 지점이 있다면 그 부분 기준으로 BFS 탐색
5. 모두 방문했다면 종료.

이렇게 구현하면 visited탐색이 반복되므로 매우매우~ 비효율적이다.

최근 접근 방법

1. visited 탐색한다.
2. 탐색 중 방문 여부 확인
   • 미방문
     • BFS 탐색 및, visited 표시
   • 방문
     • 다음 확인

이렇게 해주면 visited를 한 번만 탐색해줘도 모두 탐색할 수 있다.

한번의 visited 탐색으로 모두 방문할 수 있으며 bfs로 방문했던 곳은 visited 방문 여부 확인으로 넘어갈 수 있다.

구현

최근에 자바에 익숙해질 겸 토이프로젝트를 진행하면서 자바에 좀 친숙해졌다.

이번엔 파이썬 대신 자바로 구현했다.

장점

• scope 관점에서 자바가 파이썬보다 명확한 느낌을 받았다.

• 그리고 접근제어 덕분에 서브 메소드인지 확인하기 용이하다. (외부 용도 막는다는 관점에서 보면 의도에 맞게 쓰진 않는 것 같다.

• eclipse가 너무 똑똑하다.

• 클래스로 선언되어 있어서 파이썬처럼 global이나 nonlocal을 안써도 된다. (함수호출횟수 세기 같은 상황에선언해 줄 필요가 있었다.)

단점

• 파이썬에 비해 코드가 길어진다.
• 문자열 parsing이 파이썬에 비해 어렵다.

package programmers;

class Solution {
    private boolean[][] visited;
    private int[] dr = {0,0,1,-1};
    private int[] dc = {1,-1,0,0};
    private int[][] picture;
    private int m;
    private int n;

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

        this.initVisited();

        //r,c에 대해 탐색. 이렇게 탐색하면 어차피 전부 탐색함. 매 bfs마다 visited여부 모두 탐색할 필요 없음.
        for (int r=0; r<m; r++) {
            for (int c=0; c<n; c++) {
                //방문 했으면 pass getArea에서 bfs돌며 이미 방문했던 곳을 넘기는 코드.
                if (this.visited[r][c]) {
                    continue;
                }
                //색칠할 곳이 아니면 재방문 못하게 방문 표시 후 pass
                if (picture[r][c] == 0) {
                    this.visited[r][c] = true;
                    continue;
                }

                //위 두 경우가 아니라면 bfs를 돌릴 수 있는 영역. 따라서 numberOfArea 1증가.
                numberOfArea += 1;

                tempSize = getArea(r,c,picture[r][c]);

                maxSizeOfOneArea = updateMaxSizeArea(maxSizeOfOneArea, tempSize);
            }
        }


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

    public void initVisited () {
        boolean[][] visited = new boolean[m][n];

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

        this.visited = visited;
    }

    //r,c 위치에 해당하는 면적 넓이 구하는 메소드.
    public int getArea(int r, int c, int color) {
        //범위체크
        if(r<0 | r>=m |c<0 | c>=n) {
            return 0;
        }
        //방문 여부 및 동일 컬러가 아니면 종료.
        if (this.visited[r][c] | this.picture[r][c] != color) {
            return 0;
        }

        this.visited[r][c] = true;

        //r,c기준 4방향 방문시 area값 구하기
        int sum = 0;
        for (int i=0; i<4; i++) {
            int nr = r + dr[i];
            int nc = c + dc[i];
            sum += getArea(nr,nc, color);
        }

        //r,c 현재 위치 area + 4방향 area 넓이
        return 1 + sum;
    }

    private int updateMaxSizeArea(int maxSizeArea, int tempArea) {
        if (maxSizeArea < tempArea) {
            maxSizeArea = tempArea;
        }
        return maxSizeArea;
    }
}

getArea에서 4방향 탐색시 방문여부를 미리 확인하면 함수를 호출하지 않으므로 실행속도가 증가하나 가독성을 위해 패스.