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

[문제]

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

알고리즘 연습 - 카카오프렌즈 컬러링북 | 프로그래머스

[풀이방법]

 

테스트 케이스는 통과하는데 채점에서 런타임 에러가 났다.

재귀를 사용하면 안되는 것 같다. 아마 stackoverflow 에러가 발생하는 것 같다. 

 

찾아보니까 런타임 에러가 흔히 발생하는 문제인 것 같다. 

어떤 분이 최대로 주어진 값들을 넣어봤더니 스택에 함수 호출이 쌓여서 런타임 에러가 발생하는 거라고 말씀하셨다. 

 

효율적으로 코드 짜기 정말 힘든 것 같다..

 

프로그래머스는 실행시간과 메모리 제한을 알려주지 않아서 맞추기가 어렵다.. ;-(

 

---

 

삼성 문제 풀다가 카카오 문제 보니까 뭔가 생동감 있고 재밌는 것 같다. 

만만한 문제인 것 같다 하고 야심차게 풀어봤지만 런타임에러에 막혔지만..

 

딱 문제를 보면 연결 요소 구하기 / 연결영역 구하기 등 비슷한 문제들이 떠올랐다. 

 

아, 그럼 DFS로 풀면 되겠다!! 이게 바로 런타임 지옥의 시발점이었다. 

 

오히려 BFSf로 접근하는게 문제를 빠르게 풀 수 있는 길인 것 같다. 하지만 큐를 사용하면 자바에서 제공하는 큐는 실행이 느려서 실행 시간 초과가 발생한다. 그래서 priorityQueue 등을 생각하다가 스택을 사용하게 됐다. 

 

스택으로 풀면 정말 간단하게 풀렸다. (허무..)

 

---

그림의 난이도를 영역의 수로 정의하였다. (영역이란 상하좌우로 연결된 같은 색상의 공간을 의미한다.)

그림에 몇 개의 영역이 있는지와 가장 큰 영역의 넓이는 얼마인지 계산하는 프로그램을 작성해보자.

---

그냥 같은 숫자가 적힌 칸들이 상하좌우에 얼마나 연결되어있는지 찾는 문제이다. 

 

[BFS]

 

1. 스택을 생성 (클래스를 생성하지 않고 정수 x, y를 저장하는 스택을 따로 생성하여 각각 스택에 넣어준다.)
2. count = 연결된 영역의 너비 (1칸에 너비가 1로 간주함) => 나중에 최대값 비교함 
3. 칸에 적힌 값이 0이 아니고 visited (방문한 좌표를 표시) 가 false인 경우에 스택에 각 좌표의 값을 넣어주고 visited를 true로 변경한다.
4. 지역 너비를 1만큼 증가한다.(지금 좌표의 영역을 추가)
5. 영역이 새로 생겼으니 영역의 수도 증가해준다. 
6. 스택을 탐색한다. (상 하 좌 우 모두 해 주어야 한다.)

---

[재귀 사용]

class Solution {
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static int[][] picture;
    
  public int[] solution(int m, int n, int[][] picture) {
      int numberOfArea = 0;
      int maxSizeOfOneArea = 0;
        int  width = 0;
      this.picture = picture;
      
     for (int i = 0; i < m; i++) {
         for (int j = 0; j < n; j++) {
             if ( picture[i][j] != 0) {
                 width= dfs(i, j, m, n, picture[i][j]);
                 if ( maxSizeOfOneArea < width) {
                     maxSizeOfOneArea = width;
                 }
                 numberOfArea++;
             }
        }
     }
      
      int[] answer = new int[2];
      answer[0] = numberOfArea;
      answer[1] = maxSizeOfOneArea;
     
      return answer;
  }
    static int dfs(int x, int y, int m, int n, int prev) {
        int temp_count = 1;
        
        if (picture[x][y] != prev) return 0;
        picture[x][y] = 0;
        
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if (nx < 0 || nx >= m || ny < 0 || ny >= n ||  picture[nx][ny] == 0) continue;
            
            if (picture[nx][ny] != prev) continue;
            
             temp_count += dfs(nx, ny, m, n,prev);
        }
        return temp_count;
    }
}

 

[스택 사용]

import java.util.*;
class Solution {
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static int[][] picture;
    static boolean[][] visited;
    
  public int[] solution(int m, int n, int[][] picture) {
      int numberOfArea = 0;
      int maxSizeOfOneArea = 0;
        
      this.picture = picture;
      visited = new boolean[m][n];
      
      int[] answer = bfs(m, n);
      System.out.println(answer[0]);
     
      return answer;
  }
    static int[] bfs(int m, int n) {
        int[] answer = new int[2];
        Stack<Integer> sx = new Stack<>();
        Stack<Integer> sy = new Stack<>();
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int count = 0;
                if (picture[i][j] != 0 && !visited[i][j]) {
                    addComponent(sx, sy, i, j);
                    count++;
                    answer[0]++;
                }
                
                while(!sx.isEmpty()) {
                    int x = sx.pop();
                    int y = sy.pop();
                    
                    if (x > 0 && picture[x-1][y]== picture[i][j] && !visited[x-1][y]) {
                        addComponent(sx, sy, x-1, y);
                        count++;
                    }
                    
                     if (y > 0 && picture[x][y-1]== picture[i][j] && !visited[x][y-1]) {
                        addComponent(sx, sy, x, y-1);
                        count++;
                    }
                    
                     if (x < m-1 && picture[x+1][y]== picture[i][j] && !visited[x+1][y]) {
                        addComponent(sx, sy, x+1, y);
                        count++;
                    }
                    
                     if (y < n-1 && picture[x][y+1]== picture[i][j] && !visited[x][y+1]) {
                        addComponent(sx, sy, x, y+1);
                        count++;
                    }
                }
                answer[1] = Math.max(count, answer[1]);
            }
        }
        return answer;
    }
    static void addComponent(Stack<Integer> sx, Stack<Integer> sy, int x, int y) {
        sx.add(x);
        sy.add(y);
        visited[x][y] = true;
    }
}