[PS] 99클럽 코테 스터디 18일차 TIL (단지번호붙이기)

문제

문제 링크

설명

이번 문제는 그래프에 대한 정보만 주어지고 그 그래프를 탐색하는 것이 아니라 주어진 입력값에서 그래프 탐색이 이루어져야 할 부분을 찾아야 한다. 아래 그림처럼 맨 처음 항목부터 1이 적힌 부분을 탐색해야 한다.

1 부분을 만나면 이동할 수 있는 경로는 상,하,좌,우 요소에 대해 다시 탐색을 수행한다. 이때 dx dy 방식으로 방향에 대한 위치를 배열에 미리 저장해 두고 사용하면 코드가 간결해진다.

static int[][] pos = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} }; // 상하좌우
   ...
// 상하좌우 탐색
for (int i = 0; i < pos.length; i++){
  // 방향 이동 후 좌표
  int nx = x + pos[i][0];   
  int ny = y + pos[i][1];
}

dfs 함수 내에서 상,하,좌,우 좌표로 계속 갱신하면서 각각의 요소에서 다시 dfs 한다. 이때 이동 했을때의 좌표 인덱스가 graph 배열의 인덱스를 벗어나는 경우를 방지하기 위해 범위 내에 있을 경우에만 탐색하도록 한다.

// 이동한 경로가 graph 배열 범위 안에 있는지 검사
private static boolean isRange(int nx, int ny) {
  return nx >= 0 && nx < N && ny >= 0 && ny < N;
}

풀이 (DFS)

public class Main {
  static int[][] graph;
  static boolean[][] visited;
  static int N;
  static int[][] pos = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} }; // 상하좌우
  static int count;

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

    N = Integer.parseInt(br.readLine());
    graph = new int[N][N];
    visited = new boolean[N][N];

    for (int i = 0; i < N; i++) {
      String s = br.readLine();
      for (int j = 0; j < N; j++) {
        graph[i][j] = s.charAt(j) - '0';
      }
    }

    ArrayList<Integer> result = new ArrayList<>();
    // (0,0) 부터 모든 요소에 대해 dfs
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < N; j++) {
        if (!visited[i][j] && graph[i][j] == 1) {
          count = 0;
          dfs(i, j);
          result.add(count);
        }
      }
    }

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

  private static void dfs(int x, int y) {
    visited[x][y] = true;
    count++;
    // 상하좌우 탐색
    for (int i = 0; i < pos.length; i++) {
      int nx = x + pos[i][0];
      int ny = y + pos[i][1];

      if (isRange(nx, ny) && !visited[nx][ny] && graph[nx][ny] == 1) {
        dfs(nx, ny);
      }
    }
  }

  private static boolean isRange(int nx, int ny) {
    return nx >= 0 && nx < N && ny >= 0 && ny < N;
  }
}

풀이 (BFS)

public class Main {
  static int[][] graph;
  static boolean[][] visited;
  static int N;
  static int[][] pos = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} }; // 상하좌우
  static int count;

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

    N = Integer.parseInt(br.readLine());
    graph = new int[N][N];
    visited = new boolean[N][N];

    for (int i = 0; i < N; i++) {
      String s = br.readLine();
      for (int j = 0; j < N; j++) {
        graph[i][j] = s.charAt(j) - '0';
      }
    }

    ArrayList<Integer> result = new ArrayList<>();
    // (0,0) 부터 모든 요소에 대해 dfs
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < N; j++) {
        if (!visited[i][j] && graph[i][j] == 1) {
          count = 1;
          bfs(i, j);
          result.add(count);
        }
      }
    }

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

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

    while (!queue.isEmpty()) {
      int[] current = queue.poll();
      int cx = current[0];
      int cy = current[1];

      // 상하좌우 탐색
      for (int i = 0; i < pos.length; i++) {
        int nx = cx + pos[i][0];
        int ny = cy + pos[i][1];

        if (isRange(nx, ny) && !visited[nx][ny] && graph[nx][ny] == 1) {
          visited[nx][ny] = true;
          queue.offer(new int[] {nx, ny});
          count++;
        }
      }
    }
  }

  private static boolean isRange(int nx, int ny) {
    return nx >= 0 && nx < N && ny >= 0 && ny < N;
  }
}