프로그래머스 - (Java) 카카오프렌즈

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

1. 유형

BFS

2. 풀이

• 이중for문 탐색으로 1이상의 값만 bfs함수 적용
• bfs에서 같은 색의 칸으로만 이동가능

3. 코드

import java.util.*;
class Solution {
    static boolean visited[][];
    static int[][] dir={{-1,0}, {0,1}, {1,0}, {0,-1}};
    static int M,N,maxarea;
    static void bfs(int r, int c, int type, int picture[][]){
        Queue<int[]> q = new LinkedList<>();
        visited[r][c] = true;
        q.add(new int[]{r, c});
        int area=0;
        while(!q.isEmpty()){
            int cur[]  = q.poll();
            ++area;
            for(int k=0; k<4; k++){
                int nr = cur[0]+dir[k][0];
                int nc = cur[1]+dir[k][1];
                if(boundary(nr,nc) || picture[nr][nc]!=type || visited[nr][nc]) continue;
                visited[nr][nc]=true;
                q.add(new int[]{nr,nc});
            }
        }
        maxarea=Math.max(maxarea, area);
    }
    static void init(int m, int n){
        visited = new boolean[m][n];
        M=m;
        N=n;
        maxarea=0;
    }

    static boolean boundary(int nr, int nc){
        if(nr<0 || nr>=M || nc<0 || nc>=N)
            return true;
        return false;
    }

    public int[] solution(int m, int n, int[][] picture) {
        init(m,n);
        int cnt = 0;
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(!visited[i][j] && picture[i][j]>0){
                    ++cnt;
                    bfs(i, j, picture[i][j], picture);
                }
            }
        }
        int[] answer={cnt, maxarea};
        return answer;
    }
}
/*
로직
- bfs
- for range(N):
    for rnage(M):
        if not visited and picture>=1
            answer++
            bfs

bfs(r,c):
    max(area, maxarea)
*/