[Java] 2667 단지번호붙이기 DFS, BFS

1. 문제 링크 및 문제

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

1-1 문제 요약

: 연결되어 있는 1들의 그룹에 대해 몇개의 그룹인지, 그룹 당 1의 개수를 도출해내야 하는 문제

2. 해결 방법 생각해보자 ...

1. (0,0)부터 마지막(n,n)까지 반복문 생성, 1일때만 GO !
2. 1일 때 상하좌우로 이동하며 연결된 1의 개수 구하기 (DFS 사용해야겠구나!)
3. visited 배열 사용 대신 방문한 좌표는 0 으로 만들어주기

시간복잡도

인접 행렬을 사용한 DFS 를 사용했으므로, O(N^2)
N의 최댓값은 25 , 시간 제한은 1초 이므로
(N^2) = 625 는 충분히 연산 가능

3-1 DFS 코드

import java.util.*;
import java.io.*;

// 문제 요약
// 1. 주어진 맵에서, 1은 집이 있는 곳 0 은 집이 없는 곳이다.
// 2. 상하좌우로 붙어있는 1들 끼리를 단지로 칭함
// 3. 맵에서 단지의 개수를 구해야 함.

// 해결 방법
// 1. 1이고, 방문하지 않았을 때 DFS

public class Main{

	static int N; // N : 맵의 크기
	static int count = 0; // 각 단지 내 집의 개수 저장할 변수
	static int[][] arr; // 맵 입력값
	static boolean[][] visited ; // 방문 확인
	static int[] dx = {-1,0,1,0}, dy={0,-1,0,1}; // 상하좌우 탐색
	static ArrayList<Integer> result; // 각 단지에 속하는 집의 수를 저장 후 오름차순으로 출력하기 위함

	public static void main(String args[]) throws Exception{
		// 값 입력 -->
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		arr = new int[N][N];
		visited = new boolean[N][N];
		result = new ArrayList<>();
		
		for(int i=0;i<N;i++){
			char[] input = br.readLine().toCharArray();
			for(int j=0;j<N;j++){
				arr[i][j] = input[j]-'0';
			}
		}
		// 값 입력 <-- 

		// 탐색 시작
		for(int i=0;i<N;i++){
			for(int j=0;j<N;j++){
				if(arr[i][j] == 1 && !visited[i][j]){ // 1이고 방문하지 않았을 때
					count = 1; // 집의 개수 : 현재 arr[i][j] = 1개
					DFS(i,j); 
					result.add(count); // DFS 후 단지 내 집의 개수 더해줌
				}
			}
		}
		Collections.sort(result); // 오름차순
		System.out.println(result.size());
		for(int i:result)System.out.println(i);
	}


	public static void DFS(int x, int y){
		visited[x][y] = true;

		for(int i=0;i<4;i++){
			int xx = x+dx[i];
			int yy = y+dy[i];
			if(xx<0 || xx>=N || yy<0 || yy>=N || visited[xx][yy] || arr[xx][yy] == 0) continue;
			if(arr[xx][yy] == 1) {
				DFS(xx,yy);
				count += 1;
			}
		}
		
	}
}

3-2 BFS 코드

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
import java.util.Queue;
import java.util.LinkedList;
import java.awt.Point;

public class Main {

    public static int N;
    public static int[][] arr;
    public static boolean[][] visited;
    public static Queue<Point> queue = new LinkedList<>();
    public static int count = 0;
    public static ArrayList<Integer> counter;
    public static int[] dx = {1,0,-1,0};
    public static int[] dy = {0,1,0,-1};

    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        N = scan.nextInt();
        arr = new int[N][N];
        visited = new boolean[N][N];
        counter = new ArrayList<>();
        String temp;

        for (int i=0;i<N;i++){
            temp = scan.next();
            for (int j=0;j<N;j++){
                arr[i][j] = temp.charAt(j)-'0';
            }
        }

        for(int i=0;i<N;i++){
            for (int j=0;j<N;j++){
                if (arr[i][j] == 1 && !visited[i][j]){
                    bfs(i,j);
                }
            }
        }
        Collections.sort(counter);
        System.out.println(counter.size());
        for(int num:counter)System.out.println(num);

    }
 
    public static void bfs(int x, int y){
        queue.offer(new Point(x,y));
        int local_cnt = 1;
        int xx, yy;
        visited[x][y] = true;
        while(!queue.isEmpty()){
            Point now = queue.poll();
            for (int i=0;i<4;i++){
                xx = now.x + dx[i];
                yy = now.y + dy[i];
                if (xx<0 || xx>=N || yy<0 || yy>=N) continue;
                if (arr[xx][yy] == 1 && !visited[xx][yy]){
                    queue.offer(new Point(xx,yy));
                    visited[xx][yy] = true;
                    local_cnt ++;
                }
            }
        }
        counter.add(local_cnt);
    }
}