백준
2667번: 단지번호붙이기
bingual
2022. 2. 24. 22:40
반응형
풀이
여러가지 방법으로 풀 수 있지만 dfs 카테고리에 있는 문제라 dfs를 이용해서 풀었습니다.
graph[0][0] ~ graph[n-1][n-1] 까지 돌면서 방문하지 않은 곳에서 dfs를 호출합니다.
dfs 함수 안에서 재귀로 dfs가 재호출 될 때마다 연결된 단지로 전진한 것이므로 count를 1씩 증가해줍니다.
처음에 호출한 dfs가 끝나면 count를 num안에 넣고 마지막에 출력할 수 있도록 저장하고, 단지 그룹 1개를 다 탐색한 것이므로 result를 1 증가시킨뒤 count를 0으로 초기화 합니다.
자바풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
public class Main {
static int count = 0;
private static int n;
private static int[][] graph = new int[25][25];
private static boolean dfs(int x, int y) {
if (x <= -1 || x >=n || y <= -1 || y >= n) {
return false;
}
if (graph[x][y] == 1) {
graph[x][y] = 0;
count += 1;
dfs(x - 1, y);
dfs(x, y - 1);
dfs(x + 1, y);
dfs(x, y + 1);
return true;
}
return false;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
ArrayList<Integer> num = new ArrayList<>();
n = Integer.parseInt(br.readLine());
for (int i = 0; i < n; i++) {
String str = br.readLine();
for (int j = 0; j < n; j++) {
graph[i][j] = str.charAt(j) - '0';
}
}
int result = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (dfs(i, j)) {
num.add(count);
result += 1;
count = 0;
}
}
}
Collections.sort(num);
System.out.println(result);
for (int i : num) {
sb.append(i).append("\n");
}
System.out.print(sb);
}
}
파이썬
from sys import stdin
def dfs(x, y):
if x <= -1 or x >= n or y <= -1 or y >= n:
return False
if graph[x][y] == 1:
graph[x][y] = 0
global count
count += 1
dfs(x - 1, y)
dfs(x, y - 1)
dfs(x + 1, y)
dfs(x, y + 1)
return True
return False
n = int(input())
num = []
graph = [list(map(int, stdin.readline().rstrip())) for _ in range(n)]
count = 0
result = 0
for i in range(n):
for j in range(n):
if dfs(i, j) == True:
num.append(count)
result += 1
count = 0
num.sort()
print(result)
for i in num:
print(i)