문제
<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.
입력
첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.
출력
첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.
나의 풀이
바로 전에 풀었던 백준 유기농 배추 문제와 아주 유사한 문제다!
유기농 배추 문제는 이 문제에서 단지의 개수만 세어주면 끝나는 문제였다. 문제 유형이 아주 유사하기 때문에 코드에 대한 설명은 줄이고 문제를 풀면서 겪었던 어려움에 대해서 이야기를 해보도록 하겠다.
DFS
for (int x = 1; x <= N; x++) {
for (int y = 1; y <= N; y++) {
if (graph[y][x]) {
countDanJi = 0; // dfs는 0시작
//countDanJi = 1;
bfs(x, y);
list.add(countDanJi);
}
}
}
-----------------------------------------------------
public static void dfs(int x, int y) {
**graph[y][x] = false;**
countDanJi++;
for (int i = 0; i < 4; i++) {
int newX = x + dx[i];
int newY = y + dy[i];
if (graph[newY][newX]) {
dfs(newX, newY);
}
}
}dfs는 계속해서 자기 자신을 호출하기 때문에 중복 검사를 함수 내부에서 한 번만 해줘도 아무 이상이 없었다. 하지만 bfs 함수는 그렇지 않았다.
또한, dfs는 자기 자신부터 검사하기 때문에 countDanji를 0에서 출발해도 괜찮지만, bfs는 시작부터 유효한 값을 갖고 시작하기 때문에 countDanji를 1에서 출발한다.
bfs 중복 검사 부분을 코드와 함께 살펴보도록 하자
BFS
for (int x = 1; x <= N; x++) {
for (int y = 1; y <= N; y++) {
if (graph[y][x]) {
//countDanJi = 0; // dfs는 0시작
countDanJi = 1;
bfs(x, y);
list.add(countDanJi);
}
}
}
-----------------------------------------------------
public static void bfs(int x, int y) {
Queue<Node> que = new LinkedList<>();
Node node = new Node(x, y);
que.add(node);
while (!que.isEmpty()) {
x = que.peek().x;
y = que.peek().y;
**graph[y][x] = false;**
que.poll();
for (int i = 0; i < 4; i++) {
int newX = x + dx[i];
int newY = y + dy[i];
if (graph[newY][newX]) {
que.add(new Node(newX, newY));
countDanJi++;
**graph[newY][newX]=false;**
}
}
}
}bfs는 스스로를 재귀 호출하지 않기 때문에 while문 내부에서의 중복 처리가 중요하다.
처음에는 이와 같은 코드로 처리를 하였는데
public static void bfs(int x, int y) {
**grapth[y][x] = false;**
...
while (!que.isEmpty()) {
...
**graph[y][x] = false;**
for (int i = 0; i < 4; i++) {
...
if (graph[newY][newX]) {
que.add(new Node(newX, newY));
countDanJi++;
}
}
}
}이렇게 처리를 하더라도 while 내부의 중복 체크가 이전 값들을 받아와 진행하기 때문에 문제가 없을 것이라고 생각했다. 하지만 예상과 다르게 중복된 값을 카운팅하여 결과를 출력하고 있었다.
예상되는 결과값보다 값이 크다는 것은 같은 좌표를 탐색하고 있다는 것이며, 이는 중복 처리가 원활하게 이루어지지 않고 있다는 것.
즉, que.add() 가 이뤄지는 부분에서 중복 처리를 하지 않는 경우 que.poll()을 하기 전까지 que에 새로운 좌표가 들어갔다고 하더라도 그에 대한 중복처리는 하지 않고 있기 때문에 발생하는 문제였다.
이런 식으로 중복된 좌표를 카운팅하고 있었기 때문에 예상되는 결과보다 더 큰 값을 출력하고 있었던 것이다.
전체 코드
import java.io.*;
import java.util.*;
public class Baek2667 {
static int Max = 25 + 2;
static boolean[][] graph;
static boolean[][] visited;
static int[] dx = {1, -1, 0, 0};
static int[] dy = {0, 0, 1, -1};
static int countDanJi;
static class Node {
int x;
int y;
public Node(int x, int y) {
this.x = x;
this.y = y;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
graph = new boolean[Max][Max];
visited = new boolean[Max][Max];
for (int i = 1; i <= N; i++) {
String s = br.readLine();
for (int j = 1; j <= N; j++) {
graph[i][j] = s.charAt(j - 1) == '1';
}
}
List<Integer> list = new ArrayList<>();
for (int x = 1; x <= N; x++) {
for (int y = 1; y <= N; y++) {
if (graph[y][x]) {
// countDanJi = 0; // dfs는 0시작
countDanJi = 1;
bfs(x, y);
list.add(countDanJi);
}
}
}
System.out.println(list.size());
list.sort(Comparator.naturalOrder());
for (int i : list) {
System.out.println(i);
}
}
public static void dfs(int x, int y) {
graph[y][x] = false;
countDanJi++;
for (int i = 0; i < 4; i++) {
int newX = x + dx[i];
int newY = y + dy[i];
if (graph[newY][newX]) {
dfs(newX, newY);
}
}
}
public static void bfs(int x, int y) {
Queue<Node> que = new LinkedList<>();
Node node = new Node(x, y);
que.add(node);
while (!que.isEmpty()) {
x = que.peek().x;
y = que.peek().y;
graph[y][x] = false;
que.poll();
for (int i = 0; i < 4; i++) {
int newX = x + dx[i];
int newY = y + dy[i];
if (graph[newY][newX]) {
que.add(new Node(newX, newY));
countDanJi++;
graph[newY][newX]=false;
}
}
}
}
}ㅇ
