[백준 2667번/JAVA] 단지 번호 붙이기

문제

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

2667번: 단지번호붙이기

풀이

2178번 미로탐색과 유사한 문제이다. 자세한 코드 설명은 이 링크 참고

 

arr를 입력받은 값으로 초기화

 

arr(0,0)부터 bfs탐색 시작 -> 값이 0이면 그냥 리턴, 1이면 인접한 곳에 1이 몇 개인지 탐색하여 그 개수 리턴
-> bfs탐색이 한 번 끝나면 마을 하나를 다 세었다는 의미이므로 villageCount++ 해주고 houseNum배열에 리턴된 집 개수를 저장

 

houseNum을 출력할 때는 arr원소를 오름차순으로 바꿔주는 Arrays.sort()를 사용했다.

 

풀이2 (5/18)

arr를 입력받은 값으로 초기화

arr의 모든 좌표를 방문 -> 값이 1 && 아직 방문하지 않은 좌표를 bfs 탐색

bfs()는 큐를 사용해 인접 좌표를 확인, 집 개수를 리턴

 

그 다음에 마을 별 집 개수를 오름차순으로 정렬하는 부분에서 어떤 방법을 써야 할지 막힘

 

코드1

import java.util.*;
import java.util.Queue;

import java.io.*;

public class Main {        
    static Queue<Coordinate> q = new LinkedList<>();
    static boolean[][] visited;
    static int[][] arr;
    static int N;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        N = Integer.parseInt(br.readLine());
        visited = new boolean[N][N];
        arr = new int[N][N];

        int villageCount = 0; //단지 수
        int[] houseNum = new int[(N)*(N)]; //단지 내 집의 수 최대 N*N개

        //arr초기화
        for(int i=0; i<N; i++) {
            String str = br.readLine();
            for(int j=0; j<N; j++) {
                arr[i][j] = str.charAt(j)-48;
            }
        }

        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {

                if(!visited[i][j]) { //(0,0)부터 방문 안한 노드를 탐색
                    int result = bfs(i, j); //bfs탐색 결과 집의 개수 리턴

                    if(result>0) { 
                        villageCount++;
                        houseNum[villageCount] = result;
                    }
                }
            }

        }

        sb.append(villageCount).append("\n");

        Arrays.sort(houseNum);
        for(int i=0; i<houseNum.length; i++) {
            if(houseNum[i]!=0)
                sb.append(houseNum[i]).append("\n");
        }

        bw.write(sb+" ");
        bw.close();
    }

    static int bfs(int x, int y) {
        int count = 0; //집 개수

        if(arr[x][y]==0) {
            visited[x][y] = true;
            return count;
        }

        int[] dx = {0,0,1,-1};
        int[] dy = {1,-1,0,0};

        q.offer(new Coordinate(x, y));
        visited[x][y] = true;
        count++;

        while(!q.isEmpty()) {
            Coordinate c = q.poll();

            for(int i=0; i<4; i++) {
                int newX = c.x + dx[i];
                int newY = c.y + dy[i];

                if(newX<0 || newX>=N || newY<0 || newY>=N)
                    continue;

                if(arr[newX][newY]==0 || visited[newX][newY])
                    continue;

                q.offer(new Coordinate(newX, newY));
                visited[newX][newY] = true;
                count++;                
            }
        }
        return count;
    }

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

코드 2

import java.io.*;
import java.util.*;

public class Main{
    static int N;
    static int[][] arr;
    static boolean[][] check;
    static Queue<Point> q = new LinkedList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        arr = new int[N][N];
        check = new boolean[N][N];
        
        int cityCount = 0; //단지 수
        int [] cityNum = new int[N*N]; //단지 내 집의 수 최대 N*N개    
        
        //arr 초기화
        for (int i = 0; i < N; i++) {
            String str = br.readLine();
            for (int j = 0; j < N; j++) {
                arr[i][j] = str.charAt(j)-48;
            }
        }

        for (int i=0; i<N; i++) {
            for(int j=0; j<N; j++){
                if(!check[i][j] && arr[i][j]==1) { //(0,0)부터 방문 안 하고 1인 노드를 탐색
                    cityCount++; 
                    cityNum[cityCount] = bfs(i, j); //bfs 탐색 결과 집의 개수 리턴
                }
            }
        }

        bw.write(cityCount + "\n");
        
        Arrays.sort(cityNum);
        for(int i=0; i<cityNum.length; i++){
            if(cityNum[i] != 0)
                bw.write(cityNum[i] + "\n");
        }
        bw.close();
    }
    static int bfs(int x, int y){
        int[] dx = {0, 0, 1, -1};
        int[] dy = {1, -1, 0, 0};
        int count = 1;

        q.offer(new Point(x, y));
        check[x][y] = true;

        while(!q.isEmpty()) {
            Point p = q.poll();

            for(int i=0; i<4; i++){
                int newX = p.x + dx[i];
                int newY = p.y + dy[i];

                if(newX<0 || newX>=N || newY<0 || newY>=N)
                    continue;
                if(arr[newX][newY]==0 || check[newX][newY])
                    continue;
                count++;
                q.offer(new Point(newX, newY));
                check[newX][newY] = true;
            }
        }
    return count;
    }
}

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

코드 1

코드 2

 

 

코드 1과 2는 나머지 로직은 같은데, 다음 부분이 다르다.

 

코드 1 : arr의 모든 좌표를 bfs에 넣고, bfs에서 arr값이 0이면 방문처리 후 집의 개수 0리턴

코드 2:  arr값이 0인지 1인지 판단하고 나서, 1이라고 판단되는 좌표만 bfs에 넣음

 

코드 1의 속도가 더 빠르고 메모리도 절약되었다.

Note

• 2178번을 며칠 전에 풀어봐서 그런지 문제를 읽자마자 코드의 구조가 대충 그려졌다. 이번에는 수정작업 거의 없이 문제를 빨리 맞췄다.
• bfs를 queue를 사용해서 구현하는 방법에 점점 익숙해지는듯
• 집 개수가 계속 1로 초기화되길래 디버거로 추적해봤는데 bfs함수는 정상동작하고있었다. count도 제대로 세어지고, 방문체크도 문제 없었다. 알고 보니 bfs 내에 문제가 있는 게 아니고, main()에서 bfs(i,j)를 여러 번 호출해서 생긴 문제였다.
• bfs함수 두 번째 조건으로 들어가는 if(arr[newX][newY]==0 || visited[newX][newY])이 부분 AND가 아니고 OR이다. 실수X
• bfs함수 내에 이 부분을 놓쳤다. 0인 경우 bfs탐색할 필요 없이 방문체크하고 바로 리턴하면 된다. 
• if(arr[x][y]==0) { visited[x][y] = true; return count; }