BOJ(백준 온라인 저지) 2667번 with 자바[JAVA]

 

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

2667번: 단지번호붙이기

---

2178 미로 찾기와 비슷한 input 이라서 "DFS BFS 를 활용하면 되지 않을까" 먼저 생각했습니다.

 

2178 번 문제와 비슷하게 시작하는 노드에서 부터 동 서 남 북으로 이동 가능한데,

• 한 번 방문한 곳은 더이상 방문하지 않는다.
• 0이 적혀있는 곳은 방문하지 않는다.

를 지켜가며 DFS 든 BFS 든 해서 노드의 개수를 구하는 방식으로 풀었습니다.

 

2178 번 문제와 달리 해당 문제에서는 최소 거리와 같은 것이 필요하지 않고 노드의 개수만 찾으면 되는거니 비교적 구현이 간단한 DFS 로 구현해봤습니다.

 

처음 시작하는 노드의 개수는 총 단지의 개수이고

단지에 들어왔을 때 DFS 로 찾는 노드의 개수는 단지 내에 집의 개수입니다.

 

이를 LinkedList 로 저장하고 오름차순으로 출력해야 하니

오름차순 정렬을 진행 후, 출력해줍니다.

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

public class Main {

/*
@param map 인풋 저장 내용
@param visited 방문 내역
@param houseNumber 단지 내 가구의 개수, 새로운 단지를 발견할 때 마다 1로 초기화합니다.
@param complex 단지에 대한 정보를 담는 list
@param dr, dc 동서남북으로 이동하기 위한 row 와 col 의 변화율
*/

    public static int[][] map;
    public static boolean[][] visited;
    public static int houseNumber = 0;
    public static LinkedList<Integer> complex;
    public static int[] dr = {0,1,0,-1};
    public static int[] dc = {1,0,-1,0};

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        map = new int[N][N];
        visited = new boolean[N][N];
        complex = new LinkedList<>();

        for(int i=0; i<N; i++)
        {
            String s = br.readLine();
            for(int j=0; j<N; j++)
            {
                map[i][j] = s.charAt(j) - '0';
            }
        }

        for(int i=0; i<N; i++)
        {
            for(int j=0; j<N; j++)
            {
                if(map[i][j] == 1 && !visited[i][j])
                {
                    houseNumber = 1;
                    dfs(i,j);
                    complex.add(houseNumber);
                }
            }
        }

        System.out.println(complex.size());
        Collections.sort(complex);
        for(int i : complex)
            System.out.println(i);
    }

    private static void dfs(int i, int j)
    {
        visited[i][j] = true;

        int nowRow = i;
        int nowCol = j;

        for(int k=0; k<4; k++)
        {
            int nextRow = nowRow + dr[k];
            int nextCol = nowCol + dc[k];

            if(nextRow < 0 || nextRow >= visited.length || nextCol < 0 || nextCol >= visited.length)
                continue;

            if(visited[nextRow][nextCol] || map[nextRow][nextCol] == 0)
                continue;

            houseNumber++;
            dfs(nextRow, nextCol);
        }
    }
}

---

• 느낀 점

DFS BFS 를 언제 사용하는지 그리고 비교적 자유롭게 이용할 수 있게 된거 같다.