728x90
π οΈ λ¬Έμ π οΈ
ποΈ μ€λͺ ποΈ
- μμ μ μ μ°ΎκΈ°
- μ΄λ―Έμ§ μμΌλ‘ νμΈνμ λ μΌμͺ½ μ > μ€λ₯Έμͺ½ μ > μΌμͺ½ μλ > μ€λ₯Έμͺ½ μλ μ κ°μ΄ Z λͺ¨μμΌλ‘ μμ μ μ μ μ°Ύλλ€.
- νμ¬ μμΉμ κ°μ΄ 1μ΄λ©΄μ λ°©λ¬Ένμ§ μμΌλ©΄ μμ μ μ μ΄λ€.
- μμ μ μ μ κΈ°μ€μΌλ‘ κ·Έλν νμ
- BFS κ·Έλν νμ μ¬μ©
- λκ°μ μ μ μΈν μνμ’μ° μμΉμ μννΈκ° μμΌλ©΄ νμ¬ λ¨μ§μ μλ μννΈ μ μ¦κ°
- BFS νμμ΄ λλλ©΄ νμν μννΈ μ λ°ν
- νμμ΄ λλκ³ μμ§ λ¨μ μ μ μ΄ μμΌλ©΄ β ,β‘λ² κ³Όμ λ°λ³΅
- λͺ¨λ μ μ μ νμμ΄ λλλ©΄ μ¬λ°λ₯Έ νμμΌλ‘ μΆλ ₯ ν νλ‘κ·Έλ¨ μ’ λ£
β μννΈ λ¨μ§λ΄μ μλ μννΈ μλ₯Ό μ μ₯νλ λ°°μ΄(aparts[]) μ΄κΈ°ν β
π νμ΄ μ½λ π
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
public class BOJ2667 {
public static int[][] complex; //맡
public static boolean[][] visited; //λ°©λ¬Έμ¬λΆ νμΈ λ°°μ΄
public static int[] aparts; //μννΈ λ¨μ§μ μλ μννΈ μ μ μ₯
public static int aprtnum; //μννΈ λ¨μ§ λ²νΈ
static int BFS(int vx, int vy){
Queue<int[]> queue = new LinkedList<>();
//μνμ’μ°λ₯Ό νμΈνκΈ° μν λ°°μ΄
int[] X = {-1, 1, 0, 0};
int[] Y = {0, 0, -1, 1};
queue.offer(new int[] {vx, vy});
visited[vx][vy] = true;
int count = 1;
while(!queue.isEmpty()) {
int[] poll = queue.poll();
for (int t = 0; t < 4; t++) {
int x = poll[0] + X[t];
int y = poll[1] + Y[t];
if (x >= 0 && x < complex.length && y >= 0 && y < complex.length) {
if (complex[x][y] == 1 && !visited[x][y]) {
complex[x][y] = aprtnum;
queue.offer(new int[]{x, y});
visited[x][y] = true;
count++;
}
}
}
}
return count;
}
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(bf.readLine()); //μ§λμ ν¬κΈ°
complex = new int[N][N];
visited = new boolean[N][N];
/** μ§λμ ν¬κΈ°μμ λ§λ€μ΄μ§ μ μλ μ΅λμ λ¨μ§μ
* Nμ΄ μ§μμΌ κ²½μ° : N*N/2 + 1
* Nμ΄ νμμΌ κ²½μ° : (N*N+1)/2 + 1
* λ μ€ νμμΌ κ²½μ°μ μμ΄ λ μ¬μ λ‘μ°λ―λ‘ μ ν
*/
int size = ((N*N)+1)/2 + 1;
aparts = new int[size];
aprtnum = 0;
for(int i = 0; i < N; i++) {
String[] s = bf.readLine().split("");
for(int j = 0; j < N; j++) {
complex[i][j] = Integer.parseInt(s[j]);
}
}
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
if(complex[i][j] == 1 && !visited[i][j]){
aprtnum++;
aparts[aprtnum] = BFS(i, j);
}
}
}
Arrays.sort(aparts);
System.out.println(aprtnum);
for(int i = 0; i < aparts.length; i++){
if(aparts[i] != 0)
System.out.println(aparts[i]);
}
}
}
728x90
'ProgramSolve > Baekjoon' μΉ΄ν κ³ λ¦¬μ λ€λ₯Έ κΈ
[BOJ] 15657λ² - Nκ³ΌM(8) (Python) (1) | 2023.10.05 |
---|---|
[BOJ] 1911λ² - νκΈΈ 보μνκΈ° (Python) (0) | 2023.09.07 |
[BOJ] 13549λ² - μ¨λ°κΌμ§3 (Python) (0) | 2023.09.05 |
[BOJ] 1753λ² - μ΅λ¨κ²½λ‘(Python) + Dijkstra Algorithm (0) | 2023.09.04 |
[BOJ] 6064λ² - μΉ΄μ λ¬λ ₯(JAVA) (0) | 2023.03.27 |