[백준/JAVA] 2667번: 단지번호붙이기

🔺 문제

2667번: 단지번호붙이기

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N;
    static int[] dx = {0,0,-1,1}; // 좌우
    static int[] dy = {-1,1,0,0}; // 상하 
    
    static int map[][];
    static int aparts[] = new int[25*25];
    static int apartNum = 0;
    static boolean visited[][]; // 방문 저장 배열
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        N = Integer.parseInt(br.readLine());
        
        // 섬 정보 저장
        map = new int[N][N];
        for(int i = 0 ; i < N ; i++) {
            String str = br.readLine();
            for(int j = 0 ; j < N ; j++) {
                map[i][j] = str.charAt(j) - '0';
            }
        }
        
        // BFS 통해 섬 분리
        visited = new boolean[N][N];
        for(int i = 0 ; i < N ; i++) {
            for(int j = 0 ; j < N ; j++) {
                // 바다가 아니고, 방문하지 않았을 때 같은 섬으로 인식
                if(map[i][j] != 0 && !visited[i][j]) {
                    apartNum++;
                    BFS(i, j);
                }
            }
        }
        
        Arrays.sort(aparts);
        System.out.println(apartNum);
        
        for(int i = 0 ; i < aparts.length ; i++) {
            if(aparts[i] == 0) continue;
            System.out.println(aparts[i]);
        }
    }
    
    // BFS 이용해 연결된 섬 탐색
    public static void BFS(int i, int j) {
        // 2차원 LinkedList를 가진 큐 선언
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{i, j});
        visited[i][j] = true;
        aparts[apartNum]++;
        
        while(!queue.isEmpty()) {
            int[] now = queue.poll();
            
            int x = now[0];
            int y = now[1];
            
            for(int d = 0 ; d < 4 ; d++) {
                int newX = x + dx[d];
                int newY = y + dy[d];
                
                if(0 <= newX && newX  < N  && 0 <= newY && newY < N) {
                    // 방문 X & 바다 X이면 같은 섬 취급
                    if(!visited[newX][newY] && map[newX][newY] != 0) {
                        queue.add(new int[]{newX, newY});
                      visited[newX][newY] = true;
                        aparts[apartNum]++;
                    }
                }
            }
        }
    }
}

✅ 해결 아이디어
✔ DFS / BFS

 

---

🔺 다른 풀이들

- DFS 풀이도!

[백준] 2667번 단지번호붙이기 Java (DFS, BFS)

 

 

- 과정 설명

[Java] 백준 2667번 [단지번호붙이기] 자바

 

 

- 2차원 LinkedList인 Queue<int[]> 대신 Point 클래스 이용하셨다.

백준 2667 자바 JAVA 단지 번호 붙이기 알고리즘

---

💬 느낀 점

악..... 한 번에 풀어보고 싶군...

 

 

1회독	2회독	3회독	4회독	5회독
V	6.15	8.31

 

 

( + 6.15 2회독)

DFS로 풀어보았다..

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] dx = {0, 0, -1, 1};  // 좌우
    static int[] dy = {1, -1, 0, 0};  // 상하
    
    static int N;
    static char[][] map;        // 단방향 인접 행렬
    static boolean[][] visited; // 방문 배열
    
    static int[] house = new int[25*25];    // 🔔 단지내 집 수 저장 배열
    static int houseNum = 0;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        N = Integer.parseInt(br.readLine());
        map = new char[N][N];
        visited = new boolean[N][N];
        
        // 입력 받고 인접 행렬 채우기
        for(int i = 0 ; i < N ; i++) {
            char[] ch = br.readLine().toCharArray();
            
            for(int j = 0 ; j < ch.length ; j++) {
                map[i][j] = ch[j];
            }
        }
        
        // 각 점에 대해 dfs 수행 횟수 계산하기
        for(int i = 0 ; i < N ; i++) {
            for(int j = 0 ; j < N ; j++) {
                if(!visited[i][j] && map[i][j] == '1') {
                    houseNum++;
                    dfs(i, j);
                }
            }
        }
        
        Arrays.sort(house);    // 오름차순 정렬
        System.out.println(houseNum);
        
        for(int h : house) {
            if(h == 0) continue;
            sb.append(h).append("\n");
        }
        System.out.println(sb);
    }
    
    private static void dfs(int a, int b) {
        if(visited[a][b]) return;    // 종료 조건
        
        // 🔔 아래 두 줄, 순서 유의! 🔔
        visited[a][b] = true;
        house[houseNum]++; // 🎈 놓친 부분,,
 
        for(int d = 0 ; d < 4 ; d++) {
            int x = a + dx[d];
            int y = b + dy[d];
            
            if(0 <= x && x < N && 0 <= y && y < N) {
                if(map[x][y] == '1' && !visited[x][y]) {
                    dfs(x, y);
                }                
            }
        }
    }
}

visited[a][b] = true; 와 house[houseNum]++; 순서에 유의하기!

 

 

 

( + 8.31 3회독)

BFS로 풀어보았다!

내힘내품!! (내 힘으로 내가 품..)

 

BFS 수행 횟수 = 단지수

단지에 속하는 집의 수를 PriorityQueue에 저장해서 자동으로 오름차순 정렬하게 했다.

 

코드가 더 길어지긴 했는데 메모리랑 시간을 줄였다...

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] dx = {0,0,-1,1};
    static int[] dy = {1,-1,0,0};
    
    static int N, ans;
    static int[][] map;
    static boolean[][] visited;
    
    static PriorityQueue<Integer> list = new PriorityQueue<>();
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        visited = new boolean[N][N];
 
        for(int i = 0 ; i < N ; i++) {
            String str = br.readLine();
            for(int j = 0 ; j < N ; j++) {
                map[i][j] = str.charAt(j) - '0';
            }
        }
        
        for(int i = 0 ; i < N ; i++) {
            for(int j = 0 ; j < N ; j++) {
                if(!visited[i][j] && map[i][j] == 1) {
                    ans++;
                    
                    int tmp = bfs(i, j);
                    list.add(tmp);
                }
            }
        }
        
        StringBuilder sb = new StringBuilder();
        sb.append(ans).append("\n");
        
        while(!list.isEmpty()) {
            sb.append(list.poll()).append("\n");
        }
 
        System.out.println(sb);
    }
    
 
    private static int bfs(int a, int b) {
        int cnt = 1;
        visited[a][b] = true;
        
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[] {a, b});
        
        while(!queue.isEmpty()) {
            int[] now = queue.poll();
            
            for(int d = 0 ; d < 4 ; d++) {
                int newX = now[0] + dx[d];
                int newY = now[1] + dy[d];
                
                if(newX < 0 || newY < 0 || newX >= N || newY >= N)  continue;
                if(visited[newX][newY] || map[newX][newY] == 0) continue;
                
                if(!visited[newX][newY] && map[newX][newY] != 0) {
                    visited[newX][newY] = true;
                    queue.add(new int[] {newX, newY});
                    cnt++;
                }
            }
        }
        
        return cnt;
    }
}

 

 

---

(참고)

[백준] 2667번 단지번호붙이기 Java (DFS, BFS)