프로그래머스 레벨2 카카오프렌즈 컬러링북 (JAVA) (DFS)

DFS? BFS 다댐벼 ㅋㅋ

 

지인이 DFS BFS 문제를 추천해줬다

 

 

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

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

 

바로 풀어보았다..

 

모든 코드는 GitHub 에 올려놓았다.

 

class Solution {
    static int[][] pictureArr;
    static boolean[][] visited;

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


        visited = new boolean[m][n];
        pictureArr = new int[m][n];

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

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (!visited[i][j] && pictureArr[i][j] != 0) {
                    int target = pictureArr[i][j];
                    int result = dfs(i, j, target);

                    if (result > maxSizeOfOneArea) {
                        maxSizeOfOneArea = result;
                    }

                    numberOfArea++;
                }
            }
        }
        answer[0] = numberOfArea;
        answer[1] = maxSizeOfOneArea;
        return answer;
    }

    public int dfs(int x, int y, int target) {
        int answer = 1; // 방문했따는건 한개칸이 유효하다는거

        if (x <= -1 || x >= pictureArr.length || y <= -1 || y >= pictureArr[0].length) { // 범위 벗어날시 종료처리
            return 0; // 0값
        }

        if (visited[x][y] || pictureArr[x][y] == 0) { // 방문한 곳이거나 0값이면 종료
            return 0;
        }


        if (pictureArr[x][y] == target) { // 방문 하지 않은 곳이고 현재위치가 target 확인하려는 맵의 값이랑 같으면

            //방문처리
            visited[x][y] = true;
            //상하좌우 전부 탐색 시작
            answer += dfs(x - 1, y, target); // 상
            answer += dfs(x, y - 1, target); // 좌
            answer += dfs(x + 1, y, target); // 하
            answer += dfs(x, y + 1, target); // 우

        } else {
            return 0;
        }

        return answer;
    }
}

 

boolean[][]으로 방문한 곳을 전부 방문 처리해주고

 

방문할떄마다 +1 값으로 결괏값을 재귀 함수로 뽑아냈다

 

그리고 target으로 같은 값의 노드만 탐색해서 크기를 구했다.

 

---

 

처음엔 HashMap으로 값을 저장해 가며 풀었는데

 

자꾸 채점이 틀리다는 거다..

 

알고 보니 이문제는 조건이 있었다.

 

 

 1 . 원본 picture 배열이 바뀌면 무조건 실패 처리가 되는 거 같음

2 . 전역 변수를 solution에서 전부 초기화

3 . 복사해서 사용할 배열을 long로 선언해서  picture배열을 복사해서 사용

처음 풀 때는 20분밖에 안 걸렸다 후후...

 

하지만.. 문제가 이상해서

 

풀이를 갈아엎고 다시 풀었다..

 

 

하지만 결국 문제가 이상해서 갈아엎고 다시 풀었다 ㅠㅠ

 

DFS? BFS 댐 벼..!