하루
모각코 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;
}
}
```
'19년 하계 모.각.코' 카테고리의 다른 글
모각코 3일차 (19.07.05) 웹프로그래밍 공부 (0) | 2019.07.05 |
---|---|
2019-07-05 하계모각코 세번째 차시 목표 (0) | 2019.07.05 |
모각코 2일차 (19.07.02) 웹프로그래밍 공부 (0) | 2019.07.02 |
2019-07-02 하계모각코 두번째 차시 목표 (0) | 2019.07.02 |
2019-06-28 하계모각코 첫번째 차시 목표 (0) | 2019.06.28 |
Comments