백준 2667

2667번: 단지번호붙이기

1은 집이 있는 곳을 의미하고 0은 집이 아닌 곳을 의미한다. 1을 집이라고 했을 때 집이 연결되어 있는 곳을 하나의 아파트 단지라고 한다.

이때 전체 단지의 갯수와 단지 내 집의 수를 오름차순으로 정렬하는 문제이다.

풀이

문제를 보고 BFS 문제를 해결해나가야 겠다는 큰 가닥을 잡았다.

전체 배열의 원소들을 탐색해나가면서 원소의 값이 1이고 아직 방문하지 않은 원소라면 방문하지 않은 아파트 단지라는 것이기 때문에

BFS 함수를 호출해서 인접한 연결된 아파트를 탐색해 나가면 된다고 생각했다.

 

for(int i =0;i<n;++i)
{
    for(int t = 0;t<n;++t)
    {
        if(map[i][t]==1 && visited[i][t]==false)
        {
            visited[i][t] = true;
            bfs(i,t);
            ++totalHouseCount;
        }
    }
}

전체 배열의 원소를 탐색해나가면서 원소의 값이 1이고 방문하지 않은 원소라는 것일 때의 코드이다.

해당 원소를 이제 방문했기 때문에 visited[i][t]에 true값을 줘서 체크해 준다.

그다음 해당 원소에 인접한 1을 모두 찾기 위해 bfs함수를 호출한다.

그리고 전체 단지의 개수를 파악해야 하기 때문에 현재 if 조건문에 들어왔다면 새로운 아파트 단지라는 의미이기 때문에

totalHouseCount를 증가시켜준다.

 

public static void bfs(int x,int y)
{
    Queue<Node> queue = new LinkedList<>();
    queue.offer(new Node(x,y));
    int count = 1;
    while(!queue.isEmpty())
    {
        Node node = queue.poll();
        for(int i=0;i<4;++i)
        {
            int tempX = node.x + xMove[i];
            int tempY = node.y + yMove[i];
            if(tempX < 0 || tempY < 0 || tempX>=n || tempY >=n)
            {
                continue;
            }else if(visited[tempX][tempY] || map[tempX][tempY] == 0)
            {
                continue;
            }else{
                queue.offer(new Node(tempX,tempY));
                visited[tempX][tempY] = true;
                ++count;
            }
        }
        houseCount.add(count);
    }
}

bfs 함수 코드이다. 일반적인 Queue를 이용한 BFS함수 알고리즘에다가 count값을 추가해 주었다.

count 변수는 아파트 단지 내에 있는 아파트 개수를 파악하기 위해 추가해 준 변수이다. 

if 조건문에 걸렸다는 것은 배열의 범위 밖에 있는 원소라는 의미이고 else if조건문에 걸렸다는 것은 이미 방문했거나 아파트가 존재하지 않는 0의 값을 가진 원소라는 의미이다.

앞선 2가지 조건문을 모두 넘어갔다면 해당 원소와 인접한 원소 즉 같은 아파트 단지에 있는 아파트라는 것이기 때문에 count함수를 증가시켜 준다. BFS 함수 탐색이 끝나면 houseCount 리스트에 값을 담아준다.

 

 

import java.util.*;
public class Main{
    static boolean[][] visited;
    static int[][] map;
    static int n;
    static int[] xMove = {1,-1,0,0};
    static int[] yMove = {0,0,1,-1};
    static List<Integer>houseCount = new ArrayList<>();

    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        map = new int[n][n];
        visited = new boolean[n][n];
        int totalHouseCount = 0;
        for(int i =0;i<n;++i)
        {
            String str = sc.next();
            for(int t = 0;t<str.length();++t)
            {
                map[i][t] = str.charAt(t)-'0';
            }
        }
        for(int i =0;i<n;++i)
        {
            for(int t = 0;t<n;++t)
            {
                if(map[i][t]==1 && visited[i][t]==false)
                {
                    visited[i][t] = true;
                    bfs(i,t);
                    ++totalHouseCount;
                }
            }
        }
        System.out.println(totalHouseCount);
        Collections.sort(houseCount);
        for(Integer integer : houseCount)
        {
            System.out.println(integer);
        }
    }

    public static void bfs(int x,int y)
    {
        Queue<Node> queue = new LinkedList<>();
        queue.offer(new Node(x,y));
        int count = 1;
        while(!queue.isEmpty())
        {
            Node node = queue.poll();
            for(int i=0;i<4;++i)
            {
                int tempX = node.x + xMove[i];
                int tempY = node.y + yMove[i];
                if(tempX < 0 || tempY < 0 || tempX>=n || tempY >=n)
                {
                    continue;
                }else if(visited[tempX][tempY] || map[tempX][tempY] == 0)
                {
                    continue;
                }else{
                    queue.offer(new Node(tempX,tempY));
                    visited[tempX][tempY] = true;
                    ++count;
                }
            }
            houseCount.add(count);
        }
    }
}

class Node{
    int x;
    int y;
    public Node(int x, int y)
    {
        this.x = x;
        this.y = y;
    }
}

전체코드가 꽤 긴 편이다. 그래도 BFS관련 문제를 스스로의 힘으로 처음 풀어서 조금 뿌듯하다.

대부분의 코테가 IDE의 도움 없이 푸는 문제들이 많아서 IDE 없이 연습을 조금 많이 해야겠다...