2667. 단지번호붙이기

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

2667번: 단지번호붙이기

 

일단 입력을 받아야 되는데 자바를 배운지 얼마안되서 string을 나누는법 부터 찾아봤다.

 

Scanner.next() : 공백 전까지 입력받은 문자열 리턴

Scanner.nextlint() : enter전까지 입력받은 문자열 리턴

 

string.charAt(idx) : String에서 idx위치에 해당하는 문자 출력

ex) String str = "abcd"

     char dat = str.charAt(0) // dat는 'a' 가 됨.

 

 

문제는 지금까지처럼 dfs나 bfs문제랑 비슷한데 2차원 배열을 쓰는것이 다른점인것 같다.

 

dfs 방식으로 풀었고, 지도를 저장할 배열 이외에도 방문 여부를 체크하는 배열이 필요하다.

 

// 지도 저장중..
        for(int i = 0; i < n; i++) {
            String temp = sc.next();

            for(int j = 0; j < n; j++) {
                arr[i][j] = temp.charAt(j)-'0'; // string to int
            }
        }

처음에 몰랐던 java에서 String한줄 입력받고 그것을 하나씩 나누는법.

Scanner.next(), str.CharAt() 사용.

for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                // 방문하지 않았고, 집이 존재
                if(visit[i][j] == 0 && arr[i][j] == 1) {
                    house_n = 0;
                    estate_num++;
                    dfs(i, j); // 여기서 dfs() 실행 수가 단지의 수.
                    house.push(house_n);
                }
            }
        }

i,j를 루프하면서 arr[i][j] 좌표에 집이 존재하고 && 아직 방문하지 않았으면 dfs 실행.

이때 dfs를 실행수가 단지의 수가 된다고 할수 있다.

그리고 dfs를 실행전에 그 단지의 집의 수 (house_n)을 0으로 초기화하고 dfs를 실행할때마다 1씩 더해서

dfs를 빠져나온 후의 house_n이 그 단지의 집의 총 갯수 이다.

 

집을 발견하면 dfs를 실행하고 dfs가 다 실행된 후에는 같은 단지안의 집들은 모두 이미 방문 상태가 될것이다.

그래서 dfs한번을 돌면 한 단지가 모두 방문 상태가 되므로 다음 dfs탐색은 또 다른 단지에서만 시작된다. 

 

단지 안의 집의 수를 구할때 처음에는 stack을 쓰지않고 그냥 int[] 배열을 썼더니 런타임에러가 났다.

런타임에러라 함은 보통 잘못된 배열의 참조가 있을때 일어나는데.. 대충 어디일까 짐작은 되지만 못찾겠어서 

그냥 Stack으로 고쳤더니 해결됐다.

 

static void dfs(int a, int b) {
        visit[a][b] = 1; // 방문 체크
        //house[estate_num]++; // dfs가 실행될때마다 단지 idx에 따라 house의 수 증가
        house_n++;

        // 좌,우,상,하 이동
        if(b+1 < n && arr[a][b+1] == 1 && visit[a][b+1] == 0) // 우
            dfs(a, b+1);
        if(b-1 >= 0 && arr[a][b-1] == 1 && visit[a][b-1] == 0) // 좌
            dfs(a, b-1);
        if(a-1 >= 0 && arr[a-1][b] == 1 && visit[a-1][b] == 0) // 상
            dfs(a-1, b);
        if(a+1 < n && arr[a+1][b] == 1 && visit[a+1][b] == 0) // 하
            dfs(a+1, b);

    }

현재 체크중인 집에서 좌,우,상,하 집을 봤을 때, 그 집이 존재하고 방문하지 않았으면 dfs실행.

 

---

처음 이 문제를 열었을때 실패표시가 있어서 봤더니 알고보니 거의 1년전에 알고리즘이란 것을 거의 몰랐을때 시도해본 문제였다. 그 때 아무것도 모르고 풀었을때는 거의 손도 못 댔는데 이렇게 거의 1년이 지난 후 푸니까 뭔가 감회가 새롭다 ㅋㅋ.

 

 

코드

import java.util.*;

public class Main {
    static int[][] arr; // 지도 저장
    static int[][] visit; // 방문 여부
    static Stack<Integer> house = new Stack<Integer>();
    static int house_n;
    static int n;
    static int estate_num = 0; // 단지수

    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();

        arr = new int[n][n];
        visit = new int[n][n];

        // 지도 저장중..
        for(int i = 0; i < n; i++) {
            String temp = sc.next();

            for(int j = 0; j < n; j++) {
                arr[i][j] = temp.charAt(j)-'0'; // string to int
            }
        }


        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                // 방문하지 않았고, 집이 존재
                if(visit[i][j] == 0 && arr[i][j] == 1) {
                    house_n = 0;
                    estate_num++;
                    dfs(i, j); // 여기서 dfs() 실행 수가 단지의 수.
                    house.push(house_n);
                }
            }
        }

        System.out.println(estate_num);
        
        Collections.sort(house);
        for(int x : house) System.out.println(x);

    }

    static void dfs(int a, int b) {
        visit[a][b] = 1; // 방문 체크
        
        house_n++;

        // 좌,우,상,하 이동
        if(b+1 < n && arr[a][b+1] == 1 && visit[a][b+1] == 0) // 우
            dfs(a, b+1);
        if(b-1 >= 0 && arr[a][b-1] == 1 && visit[a][b-1] == 0) // 좌
            dfs(a, b-1);
        if(a-1 >= 0 && arr[a-1][b] == 1 && visit[a-1][b] == 0) // 상
            dfs(a-1, b);
        if(a+1 < n && arr[a+1][b] == 1 && visit[a+1][b] == 0) // 하
            dfs(a+1, b);

    }
}

 

---

solution

 

솔루션에서는 dfs를 이용한것도 있고, bfs를 이용한 방법도 있었다.

일단 dfs를 이용한 방법은 Flood Fill 알고리즘 이라고 한다고 한다.

바둑, 지뢰찾기나 그림판같은 곳에서 많이 쓰이는 알고리즘이라고 한다.

 

dfs

코드 자체는 내가 한것과 거의 비슷했는데 한가지 다른것은 나는 dfs 탐색에서 다른 4방향으로 이동할때 

// 좌,우,상,하 이동
        if(b+1 < n && arr[a][b+1] == 1 && visit[a][b+1] == 0) // 우
            dfs(a, b+1);
        if(b-1 >= 0 && arr[a][b-1] == 1 && visit[a][b-1] == 0) // 좌
            dfs(a, b-1);
        if(a-1 >= 0 && arr[a-1][b] == 1 && visit[a-1][b] == 0) // 상
            dfs(a-1, b);
        if(a+1 < n && arr[a+1][b] == 1 && visit[a+1][b] == 0) // 하
            dfs(a+1, b);

이런식으로 일일히 이동했는데 솔루션에서는 

static int[] dx = {0, 0, 1, -1}; // 간선 4방향의 x축을 담당한다.
static int[] dy = {1, -1, 0, 0}; // 간선 4방향의 y축을 담당한다.

...

static void dfs(int x, int y) { // dfs 탐색
        d[x][y] = true; // 방문 마킹
        res[residx]++; // 방문 한 상황이므로 단지의 가구수의 값 증가시킨다
        for(int k = 0; k < 4; k++) { // 4방향 간선 탐색
            int nx = x + dx[k];
            int ny = y + dy[k];
            if(0 <= nx && nx < n && 0 <= ny && ny < n) { // 가장자리 체크
                if(a[nx][ny] == 1 && !d[nx][ny]) {
                    // 방문을 안했고, 데이터값이 '1'이면 dfs 진행.
                    dfs(nx, ny);
                }
            }
        }
    }

방향을 저장한 dx, dy배열을 만들어 놓고 반복문으로 한번에 처리했다.

이렇게 하면 이문제 뿐만 아니라 다른 dfs나 bfs문제도 훨씬 깔끔하게 풀수 있을것 같다.

 

bfs

 

bfs탐색을 이용한 코드는 내가 미로탐색이나 토마토에서 쓴 bfs 코드랑 비슷했고 

다른 점은 Pair을 이용한 것이었다.

 

bfs 코드를 짤때 내가 궁금했던것이 이거 였는데 java는 c++의 Pair이 없는 것 같았다.

그래서 고민하다 그냥 큐에 두개씩 넣고 두개씩 빼는 방법을 사용했는데,

솔루션에서는 그냥 직접 Pair라는 class를 만들어서 사용했다. 

 

class Pair { // Queue에 넣을 데이터 클래스
    int x, y;
    public Pair(int _x, int _y) {
        x = _x;
        y = _y;
    }
}

이렇게 Pair 클래스를 직접 만들었다.

그 후

static void bfs(int x, int y) {
        Queue<Pair> q = new LinkedList<Pair>();
        
        q.add(new Pair(x, y)); // 시작 지점을 큐에 넣는다

Queue를 Pair형으로 선언하고, Pair를 큐에 넣는다.