# BOJ02667 단지번호붙이기
https://www.acmicpc.net/problem/2667 (opens new window)
1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다.
# Location.java
좌표 정보를 관리하기 위한 Location 클래스이다.
static class Location {
private int x;
private int y;
public Location(int x, int y) {
this.x = x;
this.y = y;
}
}
# BFS 활용
너비 우선 탐색을 활용하여 단지의 수를 늘려간다. 단지를 전부 탐색하면 단지내에 존재하는 세대수를 반환한다.
private static int bfs(int x, int y) {
Queue<Location> queue = new LinkedList<>();
queue.add(new Location(x, y));
visited[x][y] = true;
int count = 1;
while (!queue.isEmpty()) {
Location location = queue.poll();
for (int i = 0; i < 4; i++) {
x = location.x + dx[i];
y = location.y + dy[i];
if (isLocation(x, y)) {
queue.add(new Location(x, y));
visited[x][y] = true;
count++;
}
}
}
return count;
}
private static boolean isLocation(int x, int y) {
if (x < 0 || x >= n || y < 0 || y >= n || visited[x][y] || graph[x][y] == 0) {
return false;
}
return true;
}
# 제출 코드
위에서 작성한 bfs 메소드를 활용하여 단지의 세대수를 저장한다.
List<Integer> departments = new ArrayList<>();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (!visited[i][j] && graph[i][j] != 0) {
departments.add(bfs(i, j));
}
}
}
정렬하여 총 단지 수와 함께 출력한다.
System.out.println(departments.size());
departments.stream()
.sorted()
.forEach(System.out::println);
아래는 최종 제출 코드이다.
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;
public class BOJ2667 {
private static int n;
private static int[][] graph;
private static boolean[][] visited;
// 이동할 네 가지 방향 정의 (상, 하, 좌, 우)
private static int[] dx = {-1, 1, 0, 0};
private static int[] dy = {0, 0, -1, 1};
static class Location {
private int x;
private int y;
public Location(int x, int y) {
this.x = x;
this.y = y;
}
}
private static int bfs(int x, int y) {
Queue<Location> queue = new LinkedList<>();
queue.add(new Location(x, y));
visited[x][y] = true;
int count = 1;
while (!queue.isEmpty()) {
Location location = queue.poll();
for (int i = 0; i < 4; i++) {
x = location.x + dx[i];
y = location.y + dy[i];
if (isLocation(x, y)) {
queue.add(new Location(x, y));
visited[x][y] = true;
count++;
}
}
}
return count;
}
private static boolean isLocation(int x, int y) {
if (x < 0 || x >= n || y < 0 || y >= n || visited[x][y] || graph[x][y] == 0) {
return false;
}
return true;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
scanner.nextLine();
graph = new int[n][n];
visited = new boolean[n][n];
for (int i = 0; i < n; i++) {
String[] row = scanner.nextLine().split("");
for (int j = 0; j < n; j++) {
graph[i][j] = Integer.parseInt(row[j]);
}
}
List<Integer> departments = new ArrayList<>();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (!visited[i][j] && graph[i][j] != 0) {
departments.add(bfs(i, j));
}
}
}
System.out.println(departments.size());
departments.stream()
.sorted()
.forEach(System.out::println);
}
}
# DFS 활용
깊이 우선 탐색을 활용하여 정적 필드로 선언된 count의 값을 증가시킨다.
private static void dfs(int x, int y) {
if (!isLocation(x, y)) {
return;
}
visited[x][y] = true;
count++;
for (int i = 0; i < 4; i++) {
dfs(x + dx[i], y + dy[i]);
}
}
private static boolean isLocation(int x, int y) {
if (x < 0 || x >= n || y < 0 || y >= n || visited[x][y] || graph[x][y] == 0) {
return false;
}
return true;
}
# 제출 코드
위에서 작성한 DFS를 활용하여 세대 수를 저장한 뒤 count를 초기화하며 단지 별 세대 수를 저장한다.
List<Integer> departments = new ArrayList<>();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (!visited[i][j] && graph[i][j] != 0) {
dfs(i, j);
departments.add(count);
count = 0;
}
}
}
출력 부분은 이전과 동일하다. 아래는 최종 제출 코드이다.
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class BOJ2667 {
private static int n, count;
private static int[][] graph;
private static boolean[][] visited;
// 이동할 네 가지 방향 정의 (상, 하, 좌, 우)
private static int[] dx = {-1, 1, 0, 0};
private static int[] dy = {0, 0, -1, 1};
private static void dfs(int x, int y) {
if (!isLocation(x, y)) {
return;
}
visited[x][y] = true;
count++;
for (int i = 0; i < 4; i++) {
dfs(x + dx[i], y + dy[i]);
}
}
private static boolean isLocation(int x, int y) {
if (x < 0 || x >= n || y < 0 || y >= n || visited[x][y] || graph[x][y] == 0) {
return false;
}
return true;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
scanner.nextLine();
graph = new int[n][n];
visited = new boolean[n][n];
for (int i = 0; i < n; i++) {
String[] row = scanner.nextLine().split("");
for (int j = 0; j < n; j++) {
graph[i][j] = Integer.parseInt(row[j]);
}
}
List<Integer> departments = new ArrayList<>();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (!visited[i][j] && graph[i][j] != 0) {
dfs(i, j);
departments.add(count);
count = 0;
}
}
}
System.out.println(departments.size());
departments.stream()
.sorted()
.forEach(System.out::println);
}
}