백준 2667번 : 단지번호붙이기

---

이번 문제는 정사각형 그래프에서 근접한 1의 총 합을 구하는 문제이다.

문제에서는 1을 집, 근접한 1의 총 합을 단지라고 표현했으며
출력해야하는 부분은 단지의 개수와 해당 단지의 집 개수이다.

문제에서 제시한 위 그림을 확인하면 이 문제를 이해하는데에는 크게 어려움이 없다.

그런데, 구현 단계에서 지금껏 최단거리 등만을 구하다가 갑자기 떨어져있는 루트를 각각 구해야 하는 상황에 맞딱뜨려 당황스러웠다.

문제는 이해가 되었으니, 일단 사용할 변수를 선언했다.

public class Main {
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
    static boolean[][] visited;
    static int[][] map;
    static int count = 0;
  ...

기본적으로 DFS와 BFS 둘 중 어느 탐색을 사용하더라도 2차원 배열로 그래프를 표현하여 풀어낼 문제이기 때문에 dx, dy로 각각 방향을 잡아준다.

조금 더 자세히 보면

• dx = {-1, 0, 1, 0} : 상(위로 1칸), 하(아래로 1칸), 좌(변동 없음), 우(변동 없음)
• dy = {0, 1, 0, -1} : 상(변동 없음), 하(변동 없음), 좌(왼쪽으로 1칸), 우(오른쪽으로 1칸)

와 같으며, 다음 위치는 반복문을 실행시킬 때

• nx = x + dx[i]
• ny = y + dy[i]

로 표현하여 구할 수 있다.

그 다음으로 정의된 멤버변수는 다음과 같다.

• visited = 그래프 방문 여부 체크
• map : 그래프
• count : 단지와 단지 내 집의 개수를 세어줄 변수

다음으로는 그래프를 우선적으로 구현하였다.

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

n = Integer.parseInt(br.readLine());

map = new int[n][n];
visited = new boolean[n][n];
 
for (int i = 0; i < n; i++) {
    String root = br.readLine();
    for (int j = 0; j < n; j++) {
        map[i][j] = Integer.parseInt(String.valueOf(root.charAt(j)));
    }
}

입력된 한 변의 길이인 n을 입력 받아 그래프 map 배열의 크기를 정하고 해당 크기 만큼 반복문을 실행시켜 그 다음부터 입력될 0과 1을 삽입한다.

이 방법이 2차원 배열로 그래프를 표현하는 기본적인 방법이다.

이후, bfs/dfs 탐색을 바로 시작하는 것이 아니라 우선 “단지”를 특정 해야하기 때문에 그래프를 전체 순회하여 1이고, 해당 위치를 방문하지 않은 경우를 이중 반복문을 통해 파악한다.

    ...
  
List<Integer> result = new ArrayList<>();
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        if (map[i][j] == 1 && !visited[i][j]) {
            dfs(i, j); // bfs(i, j)
            result.add(count);
            count = 0;
        }
    }
}

    ...

맨 처음 선언된 List는 단지 별로 집의 개수를 저장하기 위해 선언했다.

이중 반복문은 각각 그래프의 x, y 크기 만큼 진행되며 if 조건을 분기해 그래프 내 해당 좌표의 값이 1이고 방문하지 않았다면 dfs 혹은 bfs 탐색을 진행한다.

이 visited는 함수로 진입해 탐색을 하게 되면 현재 위치부터 방문 여부가 true로 변경되기 때문에 현 위치에서는 true로 방문 여부를 체크해주지 않아도 된다.

이후 탐색을 마친다면 단지 내 집 개수를 연산한 결과를 담은 count 배열을 List에 저장한다.

또한, 다음 단지 탐색 후 집의 개수를 세어주어야하기 때문에 count를 0으로 초기화 해준다.

다음으로는 가장 중요한 “탐색”이다.

1. DFS 탐색

    ...

    public static void dfs(int x, int y) {
        visited[x][y] = true;
        count++;

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx >= 0 && ny >= 0 && nx < n && ny < n) {
                if (map[nx][ny] == 1 && !visited[nx][ny]) {
                    dfs(nx, ny);
                }
            }
        }
    }
}

가장 먼저 이 함수에 진입하게 되면 재진입을 막기 위해 방문 여부를 true로 변경한다.

그 다음 count에 1을 더 해주는데, 이는 진입함과 동시에 현재 위치의 집의 개수를 더 해준 것이다.

다음 for문을 살펴보면 상,하,좌,우 각각 체크할 수 있도록 4번 진행된다.

맨 처음 설명했듯이 다음 위치를 특정하기 위해 nx와 ny 변수를 활용하고, 각각의 값은 현재 x, y좌표와 멤버 변수로 선언된 방향을 나타내는 배열의 값을 더 해준다.

이로써 nx와 ny에는 각각 다음 좌표의 위치가 저장되었으므로 조건을 분기하여 범위를 벗어나지 않는지를 체크한 다음 두 번째 조건으로 도달한 좌표의 값이 1인지, 방문은 하지 않았는지를 파악한다.

조건이 전부 true인 경우 재귀 함수를 실행한다.

이와 같은 로직이 반복되고 현재 단지 내의 집의 개수를 세어 리턴한다.

2. BFS 탐색

  ...

    public static void bfs(int x, int y) {
        Queue<int[]> q = new LinkedList<>();
        visited[x][y] = true;
        q.offer(new int[]{x, y});
        count++;

        while (!q.isEmpty()) {
            int[] cur = q.poll();
            for (int i = 0; i < 4; i++) {
                int nx = cur[0] + dx[i];
                int ny = cur[1] + dy[i];

                if (nx >= 0 && ny >= 0 && nx < n && ny < n) {
                    if (map[nx][ny] == 1 && !visited[nx][ny]) {
                        q.offer(new int[]{nx, ny});
                        visited[nx][ny] = true;
                        count++;
                    }
                }
            }
        }
    }
}

이번에는 Queue를 사용하는 BFS 탐색이다.

활용할 큐 선언 다음 DFS 탐색과 마찬가지로 현재 위치의 방문 여부를 true로 변경한다.

이 BFS 탐색은 시작 위치를 지정하는 것이 가장 중요한데, 처음 큐를 선언할 때 참조 타입으로 정수형 배열을 정의해준 이유가 여기 있다.

그래프를 탐색하는 문제이기 때문에 시작 위치도 당연히 좌표 값으로 표현해야한다.

이러한 이유로 큐에 삽입되는 시작 위치는 정수형 배열을 초기화하여 현재 위치를 삽입하는 것이다.

다음으로는 count에 1을 더해주는데 DFS 때와 마찬가지로 현재 도달한 위치를 포함시키는 작업이다.

이제 큐에 시작 위치가 삽입되었기 때문에 해당 좌표를 빼서 다음 좌표를 찾고 도달한 좌표부터 다시 시작하고… 를 반복해야한다.

이것이 BFS이다.

while 반복문 내부의 로직을 살펴보면

1. cur 배열에 시작 좌표를 저장한다. (큐의 값)
2. 상하좌우 만큼 반복하는 반복문을 실행한다.
3. 2의 반복문에서 nx, ny에 도달한 좌표를 저장한다.
   • 이는 DFS에서 사용한 방법과 동일하다. 다만, 값을 어디서 가져오는지의 차이가 있을 뿐이다.
4. DFS 탐색과 마찬가지로 범위를 벗어나지 않도록 조건문으로 잡아준다.
5. 만약 도달한 좌표의 값이 1이고, 방문하지 않았다면
6. 큐에 현재 위치를 다시 시작 좌표로 저장하고, 방문 여부를 true로 변경한다.
7. 마지막으로 도달한 집의 개수를 세는 문제이기 때문에 count에 1을 더 해준다.

와 같이 진행된다.

마지막으로 답안을 출력하기 위해 그 동안의 단지 값들이 계산된 List를 리턴하면된다.

각각 List의 길이는 단지의 개수
List 내부의 값들은 단지 내 집의 개수
를 나타내며 집의 개수는 오름차순 정렬하여 리턴한다.

Collections.sort(result);
System.out.println(result.size());
for (Integer val : result) {
    System.out.println(val);
}

전체 소스 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
  static int[] dx = {-1, 0, 1, 0};
  static int[] dy = {0, 1, 0, -1};
  static boolean[][] visited;
  static int[][] map;
  static int n, count = 0;

  public static void main(String[] args) throws java.io.IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    n = Integer.parseInt(br.readLine());

    map = new int[n][n];
    visited = new boolean[n][n];

    for (int i = 0; i < n; i++) {
      String root = br.readLine();
      for (int j = 0; j < n; j++) {
        map[i][j] = Integer.parseInt(String.valueOf(root.charAt(j)));
      }
    }

    List<Integer> result = new ArrayList<>();
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        if (map[i][j] == 1 && !visited[i][j]) {
          dfs(i, j);
          //bfs(i, j);
          result.add(count);
          count = 0;
        }
      }
    }

    Collections.sort(result);
    System.out.println(result.size());
    for (Integer val : result) {
      System.out.println(val);
    }
  }

  public static void dfs(int x, int y) {
    visited[x][y] = true;
    count++;

    for (int i = 0; i < 4; i++) {
      int nx = x + dx[i];
      int ny = y + dy[i];

      if (nx >= 0 && ny >= 0 && nx < n && ny < n) {
        if (map[nx][ny] == 1 && !visited[nx][ny]) {
          dfs(nx, ny);
        }
      }
    }
  }

  // + bfs method
  public static void bfs(int x, int y) {
    Queue<int[]> q = new LinkedList<>();
    visited[x][y] = true;
    q.offer(new int[]{x, y});
    count++;

    while (!q.isEmpty()) {
      int[] cur = q.poll();
      for (int i = 0; i < 4; i++) {
        int nx = cur[0] + dx[i];
        int ny = cur[1] + dy[i];

        if (nx >= 0 && ny >= 0 && nx < n && ny < n) {
          if (map[nx][ny] == 1 && !visited[nx][ny]) {
            q.offer(new int[]{nx, ny});
            visited[nx][ny] = true;
            count++;
          }
        }
      }
    }
  }
}

---

아무래도 DFS/BFS 탐색 알고리즘에 약해 해당 문제를 집중적으로 풀고 있다보니 설명이 길어진다.

약한 만큼 내가 이해하려고 쓰는 글이기 때문인데, 기억하기 위해 기록하는 만큼 크게 여의치 않는다.

여전히 내가 푼 이전 문제들을 참고해서 구현하긴 하지만 확실히 탐색 알고리즘 위주로 풀어보니 파악하기가 이전 보다는 수월하다.

결국 가장 중요한 것은 DFS = 재귀 / BFS = 큐 를 사용한다는 것이고, 특히나 BFS는 시작 위치가 중요한 것 같다.