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

#2 

visited배열 안쓰고 map의 값을 toggling 시켜줌

 

 

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;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
 
 
 
public class Main {
        
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    
    static int N; 
    static int[][] map;
    static int houseNum;
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};
    
    private static void DFS(int x, int y) {
        houseNum++;
        map[x][y] = 0;
        
        for(int i=0; i<4; i++) {
            int nx = x+dx[i];
            int ny = y+dy[i];
            if(map[nx][ny]==1) {
                DFS(nx, ny);
            }
        }
    }
    
    private static void BFS(int x, int y) {
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[] {x,y});
        map[x][y] = 0;
        
        while(!q.isEmpty()) {
            int[] curr = q.poll();
            houseNum++;
            
            for(int i=0; i<4; i++) {
                int nx = curr[0]+dx[i];
                int ny = curr[1]+dy[i];
                if(map[nx][ny]==1) {
                    q.offer(new int[] {nx,ny});
                    map[nx][ny]=0;
                }
            }
        }
        
    }
    
    public static void main(String[] args) throws IOException{
        N = stoi(br.readLine());
        map = new int[N+2][N+2];
        
        for(int i=1; i<=N; i++) {
            char[] arr = br.readLine().toCharArray();
            for (int j=1; j<=N; j++) {
                map[i][j] = arr[j-1]-'0';
//                System.out.print(map[i][j]);
            }
//            System.out.println();
        }
        
        List<Integer> resList = new ArrayList<>();
        for(int i=1; i<=N; i++) {
            for(int j=1; j<=N; j++) {
                if(map[i][j]==1) {
                    houseNum = 0;
//                    DFS(i,j);
                    BFS(i,j);
                    resList.add(houseNum);
                }
            }
        }
        
        Collections.sort(resList);
        System.out.println(resList.size());
        for (Integer i : resList) {
            System.out.println(i);
        }
        
        
//        bw.write("");
//        bw.flush();
//        bw.close();
    }
 
    private static int stoi(String input) {
        return Integer.parseInt(input);
    }
}

 

#1 

2차원 배열 visited 사용

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;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
 
 
public class Main {
        
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    
    static int[][] complex;
    static boolean[][] visited;
    static List<Integer> list = new ArrayList<>();
    static int[] dx = {0, 0, 1, -1 };
    static int[] dy = {1, -1, 0, 0 };
    static int houseNum, N;
    
    static void DFS(int y, int x) {
        visited[y][x]=true;
        houseNum++;
        
        
        for(int k=0; k<=3; k++) {
            int nx = x+dx[k];
            int ny = y+dy[k];
            if(!visited[ny][nx] && complex[ny][nx]==1) {
                DFS(ny, nx);
            }
        }
        
        
    }
    
    static void BFS(int y, int x) {
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{y,x});
        visited[y][x] = true;
        
        while(!q.isEmpty()) {
            int[] preXY = q.poll();
            houseNum++;
            
            for(int k=0; k<=3; k++) {
                int nx = preXY[1]+dx[k];
                int ny = preXY[0]+dy[k];
                if(!visited[ny][nx] && complex[ny][nx]==1) {
                    q.offer(new int[]{ny,nx});
                    visited[ny][nx] = true;
                }
            }
        }
        
        
        
    }
    
    public static void main(String[] args) throws IOException{
        N = Integer.parseInt(br.readLine());
        
        complex = new int[N+2][N+2];
        visited = new boolean[N+2][N+2];
        
        for(int i=1; i<=N; i++) {
            char[] arr = br.readLine().toCharArray();
            for (int j = 1; j <= N; j++) {
                complex[i][j] = arr[j-1]-'0';
            }
        }
        
        for(int i=1; i<=N; i++) {
            for(int j=1; j<=N; j++) {
                if(!visited[i][j] && complex[i][j]==1) {
                    DFS(i, j);
//                    System.out.println(houseNum);
                    list.add(houseNum);
                    houseNum=0;
                }
            }
        }
//        Collections.sort(list);
//        System.out.println(list.size());
//        for (Integer num : list) {
//            System.out.println(num);
//        }
//        
        list.clear();
        visited = new boolean[N+2][N+2];
        
        for(int i=1; i<=N; i++) {
            for(int j=1; j<=N; j++) {
                if(!visited[i][j] && complex[i][j]==1) {
                    BFS(i, j);
//                    System.out.println(houseNum);
                    list.add(houseNum);
                    houseNum=0;
                }
            }
        }
        
        Collections.sort(list);
        System.out.println(list.size());
        for (Integer num : list) {
            System.out.println(num);
        }
        
        
        
//        bw.write("");
//        bw.flush(); 
//        bw.close();
    }
}