ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [백준 2667 : 단지번호 붙이기] Java, BFS
    백준 알고리즘 2018. 11. 14. 19:53

    Queue를 이용하여 BFS로 풀었습니다! 


    Main함수에서는,

    1) 단지를 입력 받습니다

    2) 단지 배열 값이 1이고, 이전에 방문한 적 없는 값은 BFS 함수를 호출합니다

    3) BFS를 호출할 때마다 count를 해서 그 값을 총 단지수로 출력해줍니다.

    4) ArrayList와 Collection을 이용하여 값을 오름차순으로 정렬해 각 단지 내 집의 수를 출력해줍니다.


    BFS함수에서는,

    1) 메인에서 전해준 값을 큐에 넣고, visit 체크를 합니다.

    2) 그 값의 주변(상하좌우)을 살피며 값이 1이고 방문한 적 없는 값을 Queue에 넣습니다.

    그리고 local_cnt를 증가하며 한 단지 내의 집의 개수를 카운트 합니다. 

    3) local_cnt를 ArrayList에 추가합니다.


    풀면서 번거로웠던 점은 map을 입력받을 때 입니다. 띄어쓰기가 안 되어 있어서

    String으로 받은 후 charAt과 반복문을 통해서 map[][]에 넣어주었습니다.


    +) 풀고 나서 드는 생각이지만, 총 단지 수는 그냥 ArrayList의 size를 출력해주어도 됩니다.ㅠㅠ



    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    package mnth_11;
    import java.awt.Point;
    import java.util.*;
     
    public class BJ2667 {
        static Queue<Point> q = new LinkedList<>();
        static int[][]map; 
        static int[][]visited;
        static int []dx = {-1,1,0,0};
        static int []dy = {0,0,-1,1};
        static ArrayList al = new ArrayList();
        static int N;
        public static void main(String[] args) {
            // TODO Auto-generated method stub
            Scanner scan = new Scanner(System.in);
            int call_num = 0;
            N = scan.nextInt();    
            
            map = new int[N][N];
            visited = new int[N][N];
            String temp;
            
            for(int i=0;i<N;i++) {
                temp = scan.next();
                for(int j=0;j<N;j++
                    map[i][j] = temp.charAt(j)-'0'
            }
     
            for(int i=0;i<N;i++)
                for(int j=0;j<N;j++
                    if(map[i][j] == 1 && visited[i][j] == 0) {
                        BFS(i,j);
                        call_num++;
                    }
            
            System.out.println(call_num);
            
            Collections.sort(al);
            for(int i=0;i<al.size();i++)
                System.out.println(al.get(i));
        }
        
        static void BFS(int i, int j) 
        {
            int nx,ny;
            int local_cnt = 1;
            q.offer(new Point(i,j));
            visited[i][j] = 1;
            
            while(q.isEmpty()==false
            {
                Point now;
                now = q.poll();
                
                for(int h=0;h<4;h++) {
                nx = now.x+dx[h];
                ny = now.y+dy[h];
                
                if(nx>=0&&ny>=0&&nx<N&&ny<N) {
                if(map[nx][ny] == 1 && visited[nx][ny]==0) {
                    q.offer(new Point(nx,ny));
                    visited[nx][ny] = 1;
                    local_cnt++;
                        }
                    }
                }
            }
            al.add(local_cnt);
        }
    }
    cs


Designed by Tistory.