모각코 1일차 (19.06.28) 알고리즘 공부

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

그래프 이론관련된 문제로 정사각형으로 이우어져 있는 섬과 바다 모형을 통해 섬의 개수를 세는 알고리즘을 구현하는 문제이다.

입력 값을 여러 케이스로 연속해서 받아 하나의 case 객체로 저장하여 각 케이스의 섬과 바다의 정보 중 섬에 대한 좌표 정보를 가지고 matrix를 구성하여 그래프로 표현한 뒤 DFS를 사용하여 섬의 개수를 세도록 알고리즘을 구현하였다.

try {  
while(true) {  
int w, h;  
int[][] i ;  
int count =0;
            String input;
            input = br.readLine();
            String[] data = input.split(" ");
            w = Integer.parseInt(data[0]);
            h = Integer.parseInt(data[1]);
            if(w ==0 && h ==0) {
                break;
            }
            i = new int[h][w];

            for(int j = 0; j < h; j++ ) {
                input = br.readLine();
                data = input.split(" ");
                for(int k=0; k < w; k++) {
                    if(Integer.parseInt(data[k]) == 1)
                        count++;
                    i[j][k] = Integer.parseInt(data[k]);
                }
            }
            test = out.new Case(w, h , i, count);
            result[casecount]=0;
            test.edge = new edge[test.count];
            matrix = new int[test.count][test.count];
            for(int j=0; j<test.count; j++) {
                for(int k=0; k<test.count; k++) {
                    matrix[j][k] = 0;
                }
            }

        int edge_index = 0;
        for(int j = 0; j <test.h; j++ ) {
            for(int k = 0; k < test.w; k++) {
                if(test.i[j][k] == 1) {
                    test.edge[edge_index] = out.new edge(j, k, edge_index);
                    edge_index++;
                }
            }
        }

        if(test.count>1) {
            for(int k = 0; k<test.count; k++) {
                for(int t = k+1; t<test.count; t++) {
                    if(Math.abs((test.edge[k]).index_1-(test.edge[t]).index_1)<=1 && Math.abs((test.edge[k]).index_2-(test.edge[t]).index_2)<=1) {
                        int x = test.edge[k].matrix_index;
                        int y = test.edge[t].matrix_index;
                        matrix[x][y] = 1;
                        matrix[y][x] = 1;
                    }
                }
            }
            visit= new boolean[test.count];
            result[casecount]=0;
            for(int p =0; p<test.count; p++) {
                if(!visit[p]) {
                    out.DFS(p, test.count);
                    result[casecount]++;
                }
            }
        }else if(test.count == 1){
            result[casecount] = 1;

        }else {
            result[casecount] = 0;
        }
        casecount++;
        if(casecount == result.length) {
            int[] temp = new int[result.length*2];
            System.arraycopy(result, 0, temp, 0, result.length);
            result = new int[temp.length];
            result = temp;
        }
    }
} catch (IOException e) {
        // TODO Auto-generated catch block
        e.printStackTrace();
    }

    for (int i = 0; i < casecount; i++) {
        System.out.println(result[i]);
    }
}

DFS함수

public void DFS(int q, int count) {
if(!visit[q]) {
visit[q] = true;
for(int k=0; k<count; k++) {
if(!visit[k] && matrix[q][k] == 1) {
DFS(k, count);
} }
}
return;
}

간선과 케이스 클래스 구성
```

public class Case{
    int w, h;
    edge[] edge;
    int[][] i ;
    int count;
    public Case(int w, int h, int[][] i, int count) {
        this.w = w;
        this.h =h;
        this.i = i;
        this.count = count;
    }
}


public class edge {
    int index_1, index_2;
    int matrix_index;
    public edge(int a , int b, int edge_index) {
        index_1 = a;
        index_2 = b;
        matrix_index = edge_index;
    }
}

```