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

1. 문제

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

프로그래머스

 

2. 설명

DFS로 순환해서 풀었다.

visited 배열 없이 풀고 싶었는데 그렇게 하니까 테스트케이스는 통관데 정답 제출하니까 오류가 난다.

왜그런지 모르겠당. 카카오 문제는 왜캐 어렵징

 

3-1. 코드 - 재귀

import java.util.*;

class Solution {
    static int picCnt;
    public int[] solution(int m, int n, int[][] picture) {
        int[] answer = new int[2];
        boolean[][] visited = new boolean[m][n];
        
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        for(int i=0; i<m; i++) {
            for(int j=0; j<n; j++) {
                if(picture[i][j] > 0 && !visited[i][j]) {
                    picCnt = 0;
                    answer[0]++;
                    dfs(m, n, picture, i, j, picture[i][j], visited);
                    pq.add(picCnt);
                }
            }
        }
        answer[1] = pq.poll();
        
        return answer;
    }
    void dfs(int m, int n, int[][] picture, int x, int y, int num, boolean[][] visited) {
        if(visited[x][y] || picture[x][y] != num) return;
        picCnt++;
        visited[x][y] = true;
        
        if(0 <= x-1) {
            dfs(m, n, picture, x-1, y, num, visited);
        }
        if(x+1 < m) {
            dfs(m, n, picture, x+1, y, num, visited);
        }
        if(0 <= y-1) {
            dfs(m, n, picture, x, y-1, num, visited);
        }
        if(y+1 < n) {
            dfs(m, n, picture, x, y+1, num, visited);
        }
    }
}

 

3-2. 코드 - 스택

import java.util.*;

class Solution {
    public int[] solution(int m, int n, int[][] picture) {
        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]) {
                    answer[0]++;
                    answer[1] = Math.max(answer[1], dfs(m, n, picture, i, j, picture[i][j], visited));
                }
            }
        }
        
        return answer;
    }
    int dfs(int m, int n, int[][] picture, int x, int y, int num, boolean[][] visited) {
        Stack<int[]> stack = new Stack<>();
        int picCnt = 0;
        stack.push(new int[] {x,y});
        visited[x][y] = true;
        
        while(!stack.isEmpty()) {
            int nx = stack.peek()[0];
            int ny = stack.peek()[1];
            stack.pop();
            picCnt++;
            
            if(0 <= nx-1 && picture[nx-1][ny] == num && !visited[nx-1][ny]) {
                stack.push(new int[] {nx-1,ny});
                visited[nx-1][ny] = true;
            }
            if(nx+1 < m && picture[nx+1][ny] == num && !visited[nx+1][ny]) {
                stack.push(new int[] {nx+1,ny});
                visited[nx+1][ny] = true;
            }
            if(0 <= ny-1 && picture[nx][ny-1] == num && !visited[nx][ny-1]) {
                stack.push(new int[] {nx,ny-1});
                visited[nx][ny-1] = true;
            }
            if(ny+1 < n && picture[nx][ny+1] == num && !visited[nx][ny+1]) {
                stack.push(new int[] {nx,ny+1});
                visited[nx][ny+1] = true;
            }
        }
        
        return picCnt;
    }
}