백준 2667 - 단지번호붙이기 (JAVA 자바)

백준 2667 - 단지번호붙이기 (JAVA 자바)

 

2667번: 단지번호붙이기

 

 

단순한 DFS 문제인줄 알았는데, 너무 어려웠어요. 

예제코드는 잘 돌아가서 돌려봤는데 계속 실패가 떠서 

댓글에 있는 반례를 가지고 코드 수정을 했습니다. 

 

아래 사항에 주의하여 진행하셔야 합니다. 

 

1. 지도는 숫자가 아닌 문자열로 들어옵니다. 문자열로 받아서 charAt 으로 잘라서 저장해야됩니다. (귀찮...)

 

2. 오름차순으로 출력을 해야합니다. Arrays.sort를 활용해서 오름차순으로 정리 후 출력하도록 합시다.

 

3. 단지가 1개인 경우에도 1개의 번호를 붙여야합니다.

    특히 아래 예시의 경우, 313개의 단지가 나와야되며 1이 313번 출력되어야 합니다.

 

25
1010101010101010101010101
0101010101010101010101010
1010101010101010101010101
0101010101010101010101010
1010101010101010101010101
0101010101010101010101010
1010101010101010101010101
0101010101010101010101010
1010101010101010101010101
0101010101010101010101010
1010101010101010101010101
0101010101010101010101010
1010101010101010101010101
0101010101010101010101010
1010101010101010101010101
0101010101010101010101010
1010101010101010101010101
0101010101010101010101010
1010101010101010101010101
0101010101010101010101010
1010101010101010101010101
0101010101010101010101010
1010101010101010101010101
0101010101010101010101010
1010101010101010101010101

   

 

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Beakjoon_danzi {
 
    static String n;
    static int N, cnt, cnt2;
    static char map[][];
    static boolean visits[][];
    static int dx[] = {-1,1,0,0};
    static int dy[] = {0,0,-1,1};
    
    public static void main(String[] args) throws IOException {
    
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        n = br.readLine();
        N = Integer.parseInt(n);
        
        map = new char [N+2][N+2];
        visits = new boolean [N+2][N+2];
        
        
        for (int i=0; i<N; i++) {
            String tmp = br.readLine();
            
            for(int j=0; j<N; j++) {
                map[i][j] = tmp.charAt(j);
            }
        }
        
        cnt=0;
        Queue <Integer> q = new LinkedList<Integer>();
        
        for (int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
                if (map[i][j]=='1' && visits[i][j] == false) {
                    cnt2=0;
                    cnt++;
                    int result = dfs(i,j);
                    q.offer(result);
                
                    
                }
            }
        }
        
    
        if (cnt == 0) {
            System.out.println(cnt);
            return;
        }else {
            System.out.println(cnt);
            int list[] = new int [cnt];
            while(!q.isEmpty()) {
                for (int i=0; i<cnt; i++) {
                    int a = q.poll();
                    list[i] = a;
                }
            }
            
            Arrays.sort(list);
            
            for (int i=0; i<list.length; i++) {
                System.out.println(list[i]);
            }
        }
 
    }
    
    
    private static int dfs(int x, int y) {
        for(int i=0; i<4; i++) {
            int new_x = x+dx[i];
            int new_y = y+dy[i];            
            if (new_x<=N && new_y<=N && new_x>=0 && new_y>=0) {
                if(visits[new_x][new_y]==false && map[new_x][new_y] == '1') {
                    visits[new_x][new_y] = true;                    
                    cnt2++;
                    dfs(new_x, new_y);
                }
            }
        }
        if (cnt2 == 0) {
            cnt2++;
        }
        
        return cnt2;
    }
}