[카카오 기출 문제]카카오프렌즈 컬러링북- 레벨 2, BFS

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

프로그래머스

 

푸는데 1시간정도 걸린 것같습니다.

일반 BFS 문제인데 백트래킹문제, BFS, DFS 문제들은 변수 한가지설정을 잘못한것으로 계속해서 에러가 한번씩 나는것같습니다.

 

 

기억해야할점들

-BFS에서 여기 코드를 보면 mapvisited[nx][ny] = true 해주는 처리를 이쪽에 해야

1 1 1 

1 1 1  

이렇게 있다고 할때 (0, 0, 1) -> (0, 1, 2) -> (1, 0, 3) -> .......... 이 과정에서 mapvisited[nx][ny]를 큐에 넣을때마다 해주지 않으면 다른 점에서 해당 점을 두번 큐에 넣을 수 있다는 것이다. 그러므로 바로바로 방문처리를 해주어야합니다. BFS에서 항상 이것을 기억합니다.

if(nx >= 0 && nx < map.length && ny >= 0 && ny < map[0].length){
    if(mapvisited[nx][ny] == false && map[nx][ny] == value ){
        mapvisited[nx][ny] = true;
        q.offer(new Node(nx, ny));        
    }
}

 

-0일떄는 처리를 안한다는 것을 기억합니다.

 

import java.io.*;
import java.util.*;
import java.util.Map.*;
class Solution {
    
    int row, col;
    int[][] map;
    boolean[][] mapvisited;
    
    //상하좌우
    int[] dx = {-1,1,0,0};
    int[] dy = {0,0,-1,1};
    int numberOfArea = 0;
    int maxSizeOfOneArea = 0;
    public int[] solution(int m, int n, int[][] picture) {
        
        map = picture;
        
        mapvisited = new boolean[m][n];
        for(int i=0; i<m;i++){
            for(int j=0; j<n;j++){
                if(mapvisited[i][j] == false && map[i][j] != 0){
                    numberOfArea += 1;
                    bfs(i,j);            
                }
            }
        }
        
        int[] answer = new int[2];
        answer[0] = numberOfArea;
        answer[1] = maxSizeOfOneArea;
        return answer;
    }
    
    public void bfs(int row, int col){
        Queue<Node> q = new LinkedList<Node>();
        q.offer(new Node(row, col));
        mapvisited[row][col] = true;
        int count = 0;
        int value = map[row][col];
        while(!q.isEmpty()){
            Node temp = q.poll();
            count+=1;
            // System.out.println(" "+temp.x+" "+temp.y+" "+count);
            for(int direction=0;direction<4;direction++){
                int nx = temp.x + dx[direction];
                int ny = temp.y + dy[direction];
                if(nx >= 0 && nx < map.length && ny >= 0 && ny < map[0].length){
                    if(mapvisited[nx][ny] == false && map[nx][ny] == value ){
                        mapvisited[nx][ny] = true;
                        q.offer(new Node(nx, ny));        
                    }
                }
            }
        }
        
        maxSizeOfOneArea = Math.max(maxSizeOfOneArea, count);   
    }
}
 
class Node{
    int x;
    int y;
    public Node(int x, int y){
        this.x=x;
        this.y=y;
    }
}