-
[백준 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를 출력해주어도 됩니다.ㅠㅠ
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970package 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 stubScanner 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 '백준 알고리즘' 카테고리의 다른 글
[백준 2455 : 지능형기차] Java, 시뮬레이션 (0) 2019.01.06 [백준 2667 : 단지번호 붙이기] Java, DFS (0) 2018.11.14 [백준1697 : 숨바꼭질] Java,BFS (0) 2018.11.10 [백준 2606:바이러스]Java, bfs (0) 2018.11.10 [백준 2606:바이러스]Java, Dfs (0) 2018.11.09