99클럽 코테 스터디 4일차 TIL (미들러): [백준][Java] 24479 알고리즘 수업 - 깊이 우선 탐색 1 - 실버2

 

문제 보기

 

 

풀이

DFS에 입문하기 위한 문제인 것 같다.

 

간선을 방문하며 순서를 기록하면 되는 문제이고 어려운 점은 없었다.

 

주의할 점은

1. 오름차순으로 정렬이 되어 있어야 한다는 것

2. 간선 정보를 리스트, 배열 중 무엇에 담을지 생각해 봐야 한다는 것

정도가 있다.

 

난 오름차순 정렬을 신경 쓰기 귀찮아서 2차원 배열에 간선 정보를 저장했었는데 메모리 초과가 났다.

아무래도 DFS를 재귀로 구현했는데 간선 정보도 boolean 2차원 배열에 담아서 최대 100,000* 100,000*1byte를 잡아먹게 되니... 메모리 초과가 나 버렸다.

 

사실 최대 간선 수가 최대 정점 수의 두 배 밖에 되지 않으니 당연히 리스트로 보관하는 게 좋긴 하다.

 

 

전체 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class Main {
  private static int count = 1;
  public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    String[] inputs = br.readLine().split(" ");
    int N = Integer.parseInt(inputs[0]);
    int M = Integer.parseInt(inputs[1]);
    int R = Integer.parseInt(inputs[2]);

    List<Integer>[] arr = new ArrayList[N + 1];
    for(int i = 1; i <= N; i++) {
      arr[i] = new ArrayList<>();
    }
    while (M-- > 0) {
      inputs = br.readLine().split(" ");

      arr[Integer.parseInt(inputs[0])].add(Integer.parseInt(inputs[1]));
      arr[Integer.parseInt(inputs[1])].add(Integer.parseInt(inputs[0]));
    }
    for(int i = 1; i <= N; i++) {
      arr[i].sort(Comparator.naturalOrder());
    }

    int[] order = new int[N + 1];
    dfs(arr, R, new boolean[N + 1], order);
    for(int i = 1; i <= N; i++) {
      bw.write(order[i] + "\n");
    }

    bw.flush();
    bw.close();

  }

  private static void dfs(List<Integer>[] arr, int r, boolean[] visited, int[] order) {
    visited[r] = true;
    order[r] = count++;
    for (int k : arr[r]) {
      if (!visited[k]) {
        dfs(arr, k, visited, order);
      }
    }
  }
}

 

 

GitHub 링크

https://github.com/MetroDefro/CodingTest_AutoSave/tree/main/%EB%B0%B1%EC%A4%80/Silver/24479.%E2%80%85%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%E2%80%85%EC%88%98%EC%97%85%E2%80%85%EF%BC%8D%E2%80%85%EA%B9%8A%EC%9D%B4%E2%80%85%EC%9A%B0%EC%84%A0%E2%80%85%ED%83%90%EC%83%89%E2%80%851

CodingTest_AutoSave/백준/Silver/24479. 알고리즘 수업 － 깊이 우선 탐색 1 at main · MetroDefro/Codi