[백준] 2667번 - 단지번호붙이기 (Java)(◎)

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

<문제 분석>

1. 정점은 집이다. 상하좌우로 탐색해서 1이면 다시 탐색을 계속한다.

2. 총 단지 수와 각 단지마다 집의 개수를 출력한다.

 

<문제 풀이>

1. 메인함수에서 for문으로 dfs 함수를 호출한다.

2. 방문처리 된 곳이면 스킵하다가 새로운 1을 만나면 새로운 단지의 시작이다.

3. 방문배열을 방문처리할 때 count++를 하다가 새로운 단지를 만나면 초기화하자.

4. 단지 내 집의 수를 오름차순으로 정렬해서 출력해야 한다.

 

<주의할 점>

1. 입력함수에서 in.nextInt()로 받으면 안되고 한줄 단위로 문자열로 받은 다음 toCharArray()로 문자배열로 변환한 후에 ch - '0'을 해서 정수형으로 변환시켜서 배열에 저장해야 한다.

2. 출력함수에서 집의 수를 오름차순으로 정렬해야 하는 것을 깜박해서 채점 시 실패했다.

 

<코드 구현>

import java.util.*;

/*
백준 2667번 : 단지번호붙이기
*/

public class Main {
    int N;
    int A[][];
    boolean visited[][];
    
	void InputData() {
        Scanner in = new Scanner(System.in);
        N = in.nextInt();
        A = new int[N][N];
        for (int i=0; i<N; i++) {
            String str = in.next();
            char[] ch = str.toCharArray();
            for (int j=0; j<N; j++) {
                A[i][j] = ch[j] - '0';
            }
        }
	}

    int num = 0;
    int count = 1;
    int dx[] = {-1, 0, 1, 0};
    int dy[] = {0, 1, 0, -1};
    void DFS(int x, int y) {
        visited[x][y] = true;
        for (int i=0; i<4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
            if (visited[nx][ny]) continue;//방문한 정점이면 스킵
            if (A[nx][ny] == 0) continue;//값이 0이면 간선이 없으므로 스킵
            count++;
            DFS(nx, ny);
        }
    }

    void Solve() {
        ArrayList<Integer> list = new ArrayList<>();
        visited = new boolean[N][N];
        for (int i=0; i<N; i++) {
            for (int j=0; j<N; j++) {
                if (A[i][j] == 0) continue;
                if (visited[i][j]) continue;
                DFS(i, j);// 새 단지 검색
                num++;// 단지 번호 업데이트
                list.add(count);// 단지 안의 집의 수 업데이트                
                count = 1;// 집수 초기화
            }
        }

        Collections.sort(list);// 단지 집의 수를 오름차순 정렬
        System.out.println(num);
        for (int x : list)
            System.out.println(x);
    }
	public static void main(String[] args) {
		Main m = new Main();
		m.InputData();
        m.Solve();
	}
}

 

<구현 #2>

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.Queue;
import java.util.LinkedList;
import java.util.ArrayList;
import java.util.Collections;

public class Main {
    static int N;
    static int map[][];
    static int dx[] = {-1, 0, 1, 0};
    static int dy[] = {0, 1, 0, -1};
    static ArrayList<Integer> list = new ArrayList<>();

    class Node {
        int x, y;
        Node (int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    
    void BFS(int x, int y, int id) {
        Queue<Node> Q = new LinkedList<>();
        map[x][y] = id;
        int count = 1;
        Q.offer(new Node(x, y));

        while (!Q.isEmpty()) {
            Node now = Q.poll();
            for (int i=0; i<4; i++) {
                int nx = now.x + dx[i];
                int ny = now.y + dy[i];
                if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
                if (map[nx][ny] != 1) continue;
                map[nx][ny] = id;
                count++;
                Q.offer(new Node(nx, ny));
            }
        }
        list.add(count);
    }
    
	void Solve() {
		int group_count = 1;
        for (int i=0; i<N; i++) {
            for (int j=0; j<N; j++) {
                if (map[i][j] == 1) {
                    group_count++;
                    BFS(i, j, group_count);
                }
            }
        }
		StringBuilder sb = new StringBuilder();
        sb.append(group_count-1).append('\n');
        Collections.sort(list);
        for (int x : list) {
            sb.append(x).append('\n');
        }
        System.out.println(sb.toString());
	}

    void inputData() throws Exception {
        InputStreamReader reader = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(reader);
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        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';
            }
        }
    }

    public static void main(String[] args) throws Exception {
        int ans = -2;
        Main m = new Main();
        m.inputData(); // 입력 받는 부분
        m.Solve();// 여기서부터 작성
    }
}