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

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

프로그래머스

 

위 문제는 이전에 풀었던 문제와 유사하다(https://lets-do-the-odessey.tistory.com/57) 이러한 문제의 경우 외워뒀던 bfs를 기계적으로 입력한 뒤 문제에 맞춰 코드를 수정하면 된다

 

토대가 되는 BFS 코드

기본적인 로직에 대해 설명하자면

1. LinkedList를 사용해 내가 방문할 노드를 큐에 등록한다
2. 맨처음엔 탐색 대상으로 메소드에 주어진 y,x를 등록
3. 그 다음 while문을 통해 큐에 더이상 남은 노드가 없을때까지 계산한다
4. 계산할때 상우하좌의 인덱스를 for문을 통해 큐에 등록한다
5. 큐에 등록하기 전 탐색 대상이 맞는지 검사한다(map에서 벗어나지않는지, 검색 대상이맞는지, 이미 방문한 노드가 아닌지)
6. 위 과정을 반복하고나면 시작한 y,x에서 영역이 얼마나 이어져있는지 return한다. 

public int BFS(int y, int x, int n, int m, int[][] map, boolean[][] check) {


        // 배열탐색 01 , 10 , 0-1, -10 -> 상우하좌
        int[] dy = {0, 1, 0, -1};
        int[] dx = {1, 0, -1, 0};

        int area = 1; // 최대 면적

        // 훑은 부분을 트래킹하기위해 Deque사용, 노드 재방문X하도록
        Deque<Point> q = new LinkedList<>();
        q.add(new Point(y, x)); // 현재 위치를 큐에 추가
        check[y][x] = true;

        while (!q.isEmpty()) {
            Point current = q.poll(); // 덱에서 탐색 대상을 꺼냄
            int ey = current.y;
            int ex = current.x;

            // 해당 탐색 대상을 사방으로 조사함 1인지 이미 체크한 노드인지
            for (int i = 0; i < 4; i++) {
                int ny = ey + dy[i];
                int nx = ex + dx[i];

                if (0 <= ny && ny < n && 0 <= nx && nx < m && map[ny][nx] == 1 && !check[ny][nx]) {
                    // 1. 탐색 대상인 y,x가 0을 넘고 2. 탐색 범위를 벗어나지않고 3. map상에서 1이며 4.체크하지 않은 대상일때
                    area += 1; // 최대면적 +1
                    check[ny][nx] = true; // 방문 표시
                    q.add(new Point(ny, nx));
                }
            }
        }

        return area;
    }

 

그리고 이러한 BFS를 호출할때는
이런식으로

1. y축 -> x축 순으로 탐색하는 2중 for문을 생성한다.
2. 특정 면적이 얼마나 이어져있는지 알기위해 BFS를 호출한다고 보면된다
3. 탐색 시작조건에 이미 방문한곳은 더이상 방문하지 않게하고 방문을 시작하는 경우 그림갯수를 +1 한다

int count = 0; // 그림 갯수
int maxValue = 0; // 그림끼리 1이 얼마나 이어져있는지 = 그림면적

        for (int j = 0; j < n; j++) {
            for (int i = 0; i < m; i++) {
                if (map[j][i] == 1 && check[j][i] == false) { // 탐색 시작 조건
                    check[j][i] = true;
                    count += 1;
                    maxValue = Math.max(maxValue, BFS(j, i, n, m, map, check));
                }
            }
        }

 

풀이

위의 기본적인 풀이에서 BFS 메소드에 targetColor가 추가됐다.
단순히 0 or 1인 map을 탐색하는게 아니라 특정 색상이 얼마나 이어져있는지 검사해야하기때문이다.

import java.util.*;

class Solution {
    public int[] solution(int m, int n, int[][] picture) {
        int[] answer = new int[2];
        // m이 세로, n이 가로
        
        boolean[][] check = new boolean[m][n]; 
        int count = 0; // 영역 가짓수
        int maxValue = 0; // 최대 영역
        
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(check[i][j] == false && picture[i][j] != 0){
                    count+= 1; // 한번 탐색할때마다 영역 가짓수 늘림
                    int area = BFS(i,j,m,n,picture,check,picture[i][j]);
                    maxValue = Math.max(maxValue,area);
                }
            }
        }
        
        answer[0] = count;
        answer[1] = maxValue;
        
        return answer;
    }
    
    private int BFS(int y, int x ,int m, int n, int[][] map, boolean[][] isVisited, int targetColor){
        // 하나의 영역이 얼마나 이어져있는지 계산해서 돌려줘야함
        // 상하좌우 설정
        int[] dy = {0,1,0,-1};
        int[] dx = {1,0,-1,0};
        
        // 영역의 크기
        int area = 1;
        // 큐에 현재 탐색 시작점을 넣고
        Queue<int[]> queue = new LinkedList<>();
        int[] point = {y,x}; // 배열 생성
        queue.add(point); // queue에 배열 추가
        isVisited[y][x] = true;
        
        // 현재 탐색 시작점에서 상하좌우을 탐색, 큐가 다 빌때까지 계속해서 탐색
        while(!queue.isEmpty()){
            int[] nowPoint = queue.poll();
            int cy = nowPoint[0];
            int cx = nowPoint[1];
            
            for(int i=0; i<4; i++){
                int ny = cy + dy[i];
                int nx = cx + dx[i];
                
                // 영역들이 그림의 너비를 넘지않고, 타겟컬러이며, 방문하지 않았을때
                if(ny >= 0 && ny < m && nx >= 0 && nx < n && isVisited[ny][nx] == false && map[ny][nx] == targetColor){
                    area+= 1;
                    int[] newPoint = {ny,nx}; // 배열 생성
                    queue.add(newPoint);
                    isVisited[ny][nx] = true;
                }
            }
        }
        
        return area;
    }
}

 

 

---

비슷한 문제로는 백준의 이문제를 추천한다

https://www.acmicpc.net/problem/1926

1926번: 그림