문제 : https://www.acmicpc.net/problem/2667
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = Integer.parseInt(scan.next());
Queue q = new LinkedList<>();
int groupCount = 0;
List res = new LinkedList<>();
Node[][] arr = new Node[n][n];
Node start = null;
for (int i = 0; i < n; i++) {
String temp = scan.next();
for (int j = 0; j < n; j++) {
int value = temp.charAt(j) - '0';
arr[i][j] = new Node(i, j, value);
if (arr[i][j].val == 1) {
start = arr[i][j];
}
}
}
while (start != null) {
groupCount++;
int count = 1;
start.val = -1;
q.offer(start);
while (!q.isEmpty()) {
Node[] aj = find(q.poll(), n, arr);
for (int i = 0; i < 4; i++) {
if (aj[i] != null) {
aj[i].val = -groupCount;
count++;
q.offer(aj[i]);
}
}
}
// for (int i = 0; i < n; i++) {
// for (int j = 0; j < n; j++) {
// System.out.print(arr[i][j].val);
// }
// System.out.println();
// }
res.add(count);
// start를 기준으로 탐색시작
start = null;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (arr[i][j].val == 1) {
start = arr[i][j];
}
}
}
}
System.out.println(groupCount);
for(int i =0 ; i < groupCount ; i ++) {
res.sort(null);
System.out.println(res.get(i));
}
}
static Node[] find(Node node, int n, Node[][] array) {
Node[] result = new Node[4];
int[] addCol = { 0, 0, -1, 1 };
int[] addRow = { -1, 1, 0, 0 };
for (int i = 0; i < 4; i++) {
int col = node.col + addCol[i];
int row = node.row + addRow[i];
if (col >= n || row >= n || col < 0 || row < 0) {
result[i] = null;
} else {
if (array[col][row].val == 1) {
array[col][row].dist = node.dist + 1;
result[i] = array[col][row];
} else {
result[i] = null;
}
}
}
return result;
}
static class Node {
int col;
int row;
int val;
int dist;
public Node(int col, int row, int val) {
super();
this.col = col;
this.row = row;
this.val = val;
}
@Override
public String toString() {
return "Node [col=" + col + ", row=" + row + ", val=" + val + ", dist=" + dist + "]";
}
}
}
'알고리즘 > 심심풀이 문제풀기' 카테고리의 다른 글
[심심풀이 백준문제풀기] 1149번 RGB거리 (0) | 2018.03.16 |
---|---|
[심심풀이 백준문제풀기] 2748번 피보나치 수 2 (0) | 2018.03.16 |
[심심풀이 백준문제풀기] 2178번 미로 탐색 (0) | 2018.03.14 |
[심심풀이 백준문제풀기] 7576번 토마토 (0) | 2018.03.14 |
[심심풀이 백준문제풀기] 1475번 방 번호 (0) | 2018.03.05 |