2667번

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

2667번: 단지번호붙이기

이 문제는 조금 헷갈리는 부분이 있었다.

1인 부분에 대해서 탐색을 모두 해야하는데 그걸 어떤식으로 해서 반복해야하는지 막막한 부분이 있었는데, 질문 게시판에서 그에 대한 해결책을 얻었다.

방법은 주어진 단지 테이블에서 각각의 위치마다 1인것에 대해 DFS나 BFS를 통해 탐색을 진행하는 방식으로 하면 된다는 것을 알았다. 즉, 단지 테이블에 1인 지점이 나오면 이에 대해 탐색을 진행하고, 탐색이 끝나면 다음으로 단지 테이블에서 1이 나오는 지점에서 탐색을 진행하여 이를 반복 적으로 수행하여 단지를 판별하는 식으로 구현하는 것이다.

 

탐색방식은 DFS, BFS구현 방식과 동일하다.

그래서 두가지 방법 모두로 풀어 보았다.

 

먼저 각각의 지점에서 인접한 노드를 추가해야하는데 이를 대신하여 각 지점에서 상하좌우로 접근하도록 좌표리스트를 만들었다.

x좌표와 y좌표로 (1,0),(-1,0),(0,1),(0,-1) 이렇게 4개의 방향을 인접 노드로 하여 탐색을 진행한다.

4개의 방향에 대해서 1인 값이 있으면 이를 0으로 바꾸어 방문처리하고, 탐색을 계속 진행하는 방식으로 하나의 지점에서 탐색을 진행하고 더 이상 인접 노드가 없어서 탐색이 불가능 하면 탐색을 끝내고, 단지의 수를 하나 증가시킨다.

그리고 다음으로 1인 지점에서 탐색을 진행하고 이를 반복한다.

이를 통해서 값을 얻고 각각의 탐색 과정에서 구한 갯수 값을 저장한다.

 

main메서드에서는 먼저 테이블을 입력 받고, 테이블 전체에 대해서 1인 지점에 대한 탐색을 진행하기 위한 반복문을 구현한다.

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int[][] table = new int[N][N];

for(int i=0; i<N; i++){
    String s = br.readLine();
    for(int j=0; j<N; j++){
        table[i][j] = Integer.parseInt(String.valueOf(s.charAt(j)));
    }
}//테이블 입력 받기
Graph g = new Graph(N,table);
int num=0;
for(int i=0; i<N; i++){
    for(int j=0; j<N; j++){
        if(table[i][j]==1){
            g.dfs(i,j,num);//dfs로 탐색
            g.bfs(i,j,num);//bfs로 탐색
            num++;//단지번호 증가
        }
    }
}

Graph객체의 필드 변수는 아래와 같다.

class Graph{
    int node;//테이블의 가로,세로 길이
    HashMap<Integer,Integer> map;//단지별 갯수 저장을 위한 맵
    int[][] table;//전체 입력 받은 테이블
    int[] dx = {-1, 0, 1, 0};//x 좌표
    int[] dy = {0, 1, 0, -1};//y 좌표
    Queue<target> queue;//BFS탐색을 위한 큐
    public Graph(int node, int[][] table){
        this.table=table;
        this.node=node;
        map = new HashMap<>();
        queue = new LinkedList<>();
    }//생성자 초기화
}

먼저 DFS로 구한 과정은 아래의 메서드로 구현했다.

public void dfs(int Rx, int Ry, int num){
    table[Rx][Ry]=0;
    map.put(num,map.getOrDefault(num,0)+1);
    for(int i=0; i<4; i++){
        int x = Rx + dx[i];
        int y = Ry + dy[i];
        if(x>=0 && y>=0 && x<node && y<node && table[x][y]==1){
            dfs(x,y,num);
        }
    }
}

1인 지점을 시작 지점으로 하기 때문에 이 부분을 방문처리를 위해 0으로 만들고 단지 번호인 num에 따라 해당 단지의 갯수를 증가시킨다.

그 다음 인접 노드인 상하좌우의 좌표를 순서대로 탐색하고, 1인 부분에 대해서 인접 노드 탐색을 반복한다.

 

그 다음 BFS로 구현한 방법은 아래와 같다.

public void bfs(int Rx, int Ry, int num){
    table[Rx][Ry]=0;
    queue.add(new target(Rx,Ry));
    while(!queue.isEmpty()){
        target tmp = queue.poll();
        map.put(num,map.getOrDefault(num,0)+1);
        for(int i=0; i<4; i++){
            int x = tmp.getX() + dx[i];
            int y = tmp.getY() + dy[i];
            if(x>=0&&y>=0&&x<node&&y<node&&table[x][y]==1){
                table[x][y]=0;
                queue.add(new target(x,y));
            }
        }
    }
}

여기서는 x,y좌표를 저장할 target 객체를 추가로 만들었다.

target객체를 큐에 집어넣고, 큐가 빌때까지 이에 대해 인접한 상하좌우 좌표에 접근하여 1인 지점을 큐에 집어넣고 방문처리로 테이블의 값을 0으로 만들고 그 값을 큐에 집어넣는 과정을 반복한다.

 

정리하자면 탐색방식은 각각 DFS,BFS의 방식을 그대로 적용하고 탐색을 main메서드에서 반복적으로 진행하는 것이다.

그래서 정답코드는 아래와 같다.

package backjoon.b2667;

import java.io.*;
import java.util.*;
public class b2667 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[][] table = new int[N][N];

        for(int i=0; i<N; i++){
            String s = br.readLine();
            for(int j=0; j<N; j++){
                table[i][j] = Integer.parseInt(String.valueOf(s.charAt(j)));
            }
        }
        Graph g = new Graph(N,table);
        int num=0;
        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                if(table[i][j]==1){
                    //g.dfs(i,j,num);
                    g.bfs(i,j,num);
                    num++;
                }
            }
        }
        System.out.println(num);
        ArrayList<Integer> var = new ArrayList<>(g.map.values());
        var.sort(Integer::compareTo);
        StringBuilder sb = new StringBuilder();
        for(int i:var){
            sb.append(i).append("\n");
        }
        System.out.println(sb);
    }
}
class Graph{
    int node;
    HashMap<Integer,Integer> map;
    int[][] table;
    int[] dx = {-1, 0, 1, 0};
    int[] dy = {0, 1, 0, -1};
    Queue<target> queue;
    public Graph(int node, int[][] table){
        this.table=table;
        this.node=node;
        map = new HashMap<>();
        queue = new LinkedList<>();
    }
    public void dfs(int Rx, int Ry, int num){
        table[Rx][Ry]=0;
        map.put(num,map.getOrDefault(num,0)+1);
        for(int i=0; i<4; i++){
            int x = Rx + dx[i];
            int y = Ry + dy[i];
            if(x>=0 && y>=0 && x<node && y<node && table[x][y]==1){
                dfs(x,y,num);
            }
        }
    }
    public void bfs(int Rx, int Ry, int num){
        table[Rx][Ry]=0;
        queue.add(new target(Rx,Ry));
        while(!queue.isEmpty()){
            target tmp = queue.poll();
            map.put(num,map.getOrDefault(num,0)+1);
            for(int i=0; i<4; i++){
                int x = tmp.getX() + dx[i];
                int y = tmp.getY() + dy[i];
                if(x>=0&&y>=0&&x<node&&y<node&&table[x][y]==1){
                    table[x][y]=0;
                    queue.add(new target(x,y));
                }
            }
        }
    }
}
class target{
    private int x;
    private int y;
    public target(int x, int y){
        this.x=x;
        this.y=y;
    }

    public int getX() {
        return x;
    }

    public void setX(int x) {
        this.x = x;
    }

    public int getY() {
        return y;
    }

    public void setY(int y) {
        this.y = y;
    }
}