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

https://www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

 

- 아래 그림과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 

- 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 

- 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 

- 대각선상에 집이 있는 경우는 연결된 것이 아니다. 

- <그림2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 

- 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램 

 

 

문제 풀이 

[백준 알고리즘] 백준 2667번 단지번호붙이기 자바(Java) - 츄르 사려고 코딩하는 집사 (tistory.com)

[백준 알고리즘] 백준 2667번 단지번호붙이기 자바(Java)

 

- 같은 부류 찾기 유형

- 배열에서 1이 발견되면 단지집의 숫자는 1이 증가하고, 1을 발견할 때 마다 1씩 증가하여 ArrayList인 result에 넣어준다.

- 이 것을 배열 끝까지 반복 

- 그렇게 되면 ArrayList에는 단지의 수만큼 저장이 될 것이고, ArrayList의 크기는 단지의 개수가 된다.

 

 

정답 

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;

public class Main {
    static int N;
    static int map[][];
    static boolean visited[][];
    //dfs를 상하좌우로 돌기 위해서 그 상하좌우의 좌표값을 담아 줌 
    static int dirY[] = {-1,1,0,0};
    static int dirX[] = {0,0,-1,1};
    static int count; //단지 집의 숫자 
    
    static ArrayList<Integer> result; //단지 집의 수 저장
    
    //dfs
    public static int dfs(int x, int y)
    {
        visited[x][y] = true;
        
        //상하좌우 확인
        for(int i=0; i<4; i++)
        {
            int new_X = x + dirX[i];
            int new_Y = y + dirY[i];
            
            if(new_X>=0 && new_Y>=0 && new_X<N && new_Y<N)
            {
                if(map[new_X][new_Y]==1 && !visited[new_X][new_Y]){
                    dfs(new_X,new_Y);
                    count++;
                }
            }
        }
        
        return count;
    }
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        visited = new boolean[N][N];
        
        //맵 정보 반영
        for(int i=0; i<N; i++)
        {
        	String input = br.readLine();
            for(int j=0; j<N; j++)
            {
                map[i][j] = input.charAt(j)-'0';
            }
        }
        
        count = 0;
        
        result = new ArrayList<>();
        
        //dfs 수행
        //map 전체 탐색 
        for(int i=0; i<N; i++)
        {
            for(int j=0; j<N; j++)
            {
            	//현재 위치의 값이 1이고 true라면 
                if(map[i][j] == 1 && !visited[i][j])
                {
                    count=1; //맨 처음이기 때문에 count 1증가 
                    dfs(i,j);
                    result.add(count);
                }
            }
        }
        
        //출력
        Collections.sort(result);
        bw.write(String.valueOf(result.size()));
        bw.newLine();
        
        for(int i=0; i<result.size(); i++)
        {
            bw.write(String.valueOf(result.get(i)));
            bw.newLine();
        }
        
        bw.flush();
        bw.close();
    }
}