인프런 커뮤니티 질문&답변

안녕하세요.

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++;
                }
            }

        }
    }
}