Cộng đồng Hỏi & Đáp của Inflearn

안녕하세요.

BFS 강의를 보고 응용하여 타사이트 문제도 도전해서 풀어보면서 적용이 되는것에 재미를 느끼고 있습니다.

하지만, 약간의 응용문제를 풀려고 하니 쉽지않네요. ㅠㅠ

프로그래머스 문제 (카카오 컬러링북) 아래 링크 걸어두었습니다.

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

-> 카카오컬러링북 BFS 문제인데 

강사님께서 강조하시던

1. 마이너스 좌표체크 2. m*n 범위체크 3. grid[x][y] 값체크(문제제시값) 을 하면 해당범위에 잘걸리지않아

카운트가 잘 되지 않고 있습니다. ㅠㅠ

코드는 적어서 올려볼게요.

피드백 주시면 감사하겠습니다 ㅠㅠ

* 추가적으로 0과 1이 아닌 아래 문제처럼 1, 2, 3 색깔별로

찾는 문제도 있으면 응용에 도움이 많이 될것같습니다.

package com.algoStudy.algo0128;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class BFSTest_04 {
    // 카카오문제
    public static void main(String[] args) {

        int m = 6, n= 4;
        int[][] grid = {
                {'1', '1', '1', '0'},
                {'1', '2', '2', '0'},
                {'1', '0', '0', '1'},
                {'0', '0', '0', '1'},
                {'0', '0', '0', '3'},
                {'0', '0', '0', '3'}
        };

        System.out.println(new BFSTest_04().solution(m, n, grid));

    }

    // 전역변수 선언
//    int m,n = 0; // 가로 세로 구하기위해 셋팅 0,0 부터 시작이면 이미 선언되어있음 6x4
    int[][] dirs = {{1,0}, {-1,0}, {0,1}, {0,-1}}; // 아래,위,오른,왼
    int size = 0;

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

        // grid에 필요한 그림 그리기 및 영역 표시 확인 후 카운트 새기
        for(int i=0; i<m; i++) {
            for(int j=0; j<n; j++) {
                if(picture[i][j] != '0') {      // 값이 해당값에 포함되어있다면, 즉 영역이라면 증가시키고 bfs 칠해주기
                    size = 0;
                    numberOfArea++;           // 육지 갯수 카운트
                    bfs(picture, m, n);       // 남은영역 0 칠해주기
                    if(maxSizeOfOneArea < size)
                        maxSizeOfOneArea = size;
                }
            }
        }

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

        System.out.println(Arrays.toString(answer));

        return answer;
    }

    private void bfs(int[][] grid, int x, int y) {
        // bfs는 큐방식을 선언해주는게 이상적
        Queue<int[]> que = new LinkedList<>();
        que.offer(new int[] {x,y});

        while(!que.isEmpty()) { // 값이 있으면
            int[] point = que.poll(); // 즉시 빼기기

            // 방향 찾아서 0으로 칠하기
            for (int[] dir : dirs) {
                int x1 = point[0] + dir[0];
                int y1 = point[1] + dir[1];
                // 1. 마이너스 좌표체크 2. m*n 범위체크 3. grid[x][y] 값체크(문제제시값)
                if (x1 >= 0 && y1 >= 0 && x > x1 && y > y1 && grid[x1][y1] != '0') {
                    grid[x1][y1] = '0';
                    que.offer(new int[] {x1, y1});
                    size++;
                }
            }

        }
    }
}