[Algorithm Study] 백준 2667

문제 출차 : https://www.acmicpc.net/problem/2667

문제 접근

위의 문제의 경우 저는 DFS로 해결했습니다. 정사각형 모양의 지도가 주어졌을 때 0의 경우 집이 없는 곳이며 1인 경우 집이 있는 곳입니다. 즉 지도의 모든 곳을 방문해보면서 지도 중 값이 1인 경우에 그 위치를 기준으로 DFS를 활용해 상하좌우로 지도를 방문하며 1의 값을 2로 변경해 방문처리 했습니다.

소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class BOJ_2667 {
    static int N;
    static int[][] map;
    static boolean[][] visited;
    static int city_cnt;
    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];
        city_cnt = 0;
        ArrayList<Integer> town = new ArrayList<>();
        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++){
                dfs(i,j);
                if(city_cnt > 0){
                    town.add(city_cnt);
                    city_cnt = 0;
                }
            }
        }
        System.out.println(town.size());
        town.sort(Comparator.naturalOrder());
        for(int i = 0; i < town.size(); i++){
            System.out.println(town.get(i));
        }
    }
    public static void dfs(int x, int y){
        if(x<0 || x >= N || y < 0 || y >= N) {
            return;
        }
        if(map[x][y] == 1){
            city_cnt++;
            map[x][y] = 2;
            dfs(x-1,y);
            dfs(x+1,y);
            dfs(x,y-1);
            dfs(x,y+1);
        }
    }
}