[JAVA] 백준 2667. 단지번호붙이기 (BFS) :: 로직/코드 - GODZ

안녕하세요 GODZ입니다.

오늘은 BFS을 이용한 문제를 풀어볼 예정입니다.

---

1. 문제

 

2. 입출력 예제

 

3. 접근

1. 단지의 탐색의 종료와 새 단지의 탐색의 시작 사이에 단지 수를 +1 합니다.

2. 각 단지의 집 수를 오름차순으로 정렬해야하기 때문에 해당 정보를 위한 자료구조를 만듭니다. 

3. 2에서 나눈 단지 번호와 집의 수가 맵핑되지 않아도 되기 때문에 Map구조가 아닌 List나 배열을 사용하셔도 좋습니다. (저는 처음에 문제를 제대로 안읽어서 HashMap을 사용했습니다.)

 

4. 로직

1. 2차원 배열을 순회하며 값이 1이고, 해당 좌표가 방문한 적이 없는 곳인 경우

2. 단지 카운트를 증가, 방문 값을 true로 바꾸고 현재 좌표를 큐에 넣습니다.

3. 큐 poll()로 값을 추출하고, 해당 단지의 집 갯수를 위해 집 카운트를 증가시킵니다.

4. 인접 4방향의 좌표를 검사합니다. (dx, dy 배열 활용)

5. 인접 좌표가 2차원 배열의 내부에 있고, 값이 1이고, 방문 값이 false인 경우

6. 방문 값을 true로 바꾸고 인접 좌표를 큐에 넣습니다.

7. 3번으로 가서 반복합니다.

8. 한 단지에 대한 탐색이 끝나면(큐가 비어있을 때) 집 갯수를 0으로 초기화하고 1번으로 가서 반복합니다.

9. 2차원 배열의 순회가 끝나면, 단지 값을 출력하고 각 단지에 대한 집 수를 오름차순으로 정렬한 후 출력합니다.

 

 

5. 코드

* 저는 단지를 key, 집 수를 value로 하는 HashMap을 통해 구현했습니다. 4의 로직과 약간의 차이가 있으니 감안하셔서 참고 부탁드립니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.StringTokenizer;
 
class Pos {
    int nPos;
    int mPos;
    public Pos(int n, int m) {
        this.nPos = n;
        this.mPos = m;
    }
}
 
public class Main {
    static int N;
    static int[] dirN = {-1, 1, 0, 0};    // 상,하,좌,우 순서
    static int[] dirM = {0, 0, -1, 1};    // 상,하,좌,우 순서
    
    static int[][] map;
    static boolean[][] visited;
    static LinkedList<Pos> queue;
    static Map<Integer, Integer> res;
    static int areaCnt;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine().trim());
        
        N = Integer.parseInt(st.nextToken());
        
        map = new int[N][N];
        visited = new boolean[N][N];
        queue = new LinkedList<>();
        res = new HashMap<Integer, Integer>();
        areaCnt = 1;
        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine().trim());
            String s = st.nextToken();
            for(int j = 0; j < N; j++) {
                map[i][j] = s.charAt(j) - '0';
            }
        }
        solveBFS();
//        System.out.println(res);
        System.out.println(res.size());
        
        ArrayList<Integer> keys = new ArrayList<>(res.keySet()); 
        Collections.sort(keys, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return res.get(o1) - res.get(o2);
            }
        });
        
        for(int k : keys) {
            System.out.println(res.get(k));
        }
    }
 
    private static void solveBFS() {
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++) {
                Pos currPos = new Pos(i, j);
                // i, j가 방문한 적이 없음 && 집인 좌표
                if(boundaryCheck(currPos) && !visited[i][j]) {
                    // 새로운 구역이므로 areaCnt에 대한 map 생성
                    res.put(areaCnt, 0);
                    visited[i][j] = true;
                    queue.add(currPos);
                    while(!queue.isEmpty()) {
                        // 인접한 구간을 찾음, 구역 하나 씩 증가
                        res.put(areaCnt, res.get(areaCnt) + 1);
                        currPos = queue.poll();
                        for(int d = 0; d < 4; d++) {
                            Pos nextPos = new Pos(currPos.nPos + dirN[d], currPos.mPos + dirM[d]);
                            if(boundaryCheck(nextPos) && !visited[nextPos.nPos][nextPos.mPos]) {
                                queue.add(nextPos);
                                visited[nextPos.nPos][nextPos.mPos] = true;
                            }
                        }
                    }
                    // 더 이상 인접해있는 지점이 없음, 다음 영역으로
                    areaCnt++;
                }
            }
        }
    }
 
    private static boolean boundaryCheck(Pos pos) {
        boolean res = true;
        if(pos.nPos < 0 || pos.mPos < 0 || pos.nPos >= N || pos.mPos >= N || map[pos.nPos][pos.mPos] == 0) {
            res = false;
        }
        return res;
    }
}
 

 

 

6. 결과