지금의 기록이 미래의 자산이 된다.

• [solved.ac] Class3++ 1260. DFS와 BFS

  2023-11-30

  devFancy

  Algorithm
  • 성능 요약
  • 구분
  • Answer Code1(2023.02.09)
  • Answer Code2(2023.11.30)
  • Review
  • Reference

  문제 링크

  성능 요약

  • 메모리: 24156 KB, 시간: 368 ms

  구분

  • 그래프 이론(graphs), 그래프 탐색(graph_traversal), 너비 우선 탐색(bfs), 깊이 우선 탐색(dfs)

  Answer Code1(2023.02.09)

  import java.io.*;
  import java.util.*;
  
  public class Main {
      static int [][] check; //간선 연결상태
      static boolean [] checked; //확인 여부
      static int n; //정점 개수
      static int m; //간선 개수
      static int start; // 시작정점
  
      public static void main(String[] args) throws IOException {
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  
          StringTokenizer st = new StringTokenizer(br.readLine());
          n = Integer.parseInt(st.nextToken());
          m = Integer.parseInt(st.nextToken());
          start = Integer.parseInt(st.nextToken());
  
          check = new int[1001][1001]; // 좌표를 그대로 받아들이기 위해 +1 해서 선언
          checked = new boolean[1001]; // 초기값 : false
  
          //간선 연결상태 저장
          for(int i = 0; i < m; i++) {
              StringTokenizer str = new StringTokenizer(br.readLine());
  
              int x = Integer.parseInt(str.nextToken());
              int y = Integer.parseInt(str.nextToken());
  
              check[x][y] = check[y][x] = 1;
          }
  
          //dfs 호출
          dfs(start);
  
          checked = new boolean[1001]; // 확인상태 초기화
          System.out.println(); // 줄바꿈
  
          //bfs 호출
          bfs(start);
      }
  
      //시작점을 변수로 받아 확인, 출력 후 다음 연결점을 찾아 시작점을 변경하여 재호출
      public static void dfs(int start) {
          checked[start] = true;
          System.out.print(start + " ");
  
          for(int j = 1; j <= n; j++) {
              if(check[start][j] == 1 && checked[j] == false) {
                  dfs(j);
              }
          }
      }
  
      public static void bfs(int start) {
          Queue<Integer> queue = new LinkedList<Integer>();
  
          queue.offer(start); // 시작점도 Queue에 넣어야 함
          checked[start] = true;
  
          System.out.print(start + " ");
  
          //Queue가 비어있을 때까지 반복. 방문 정점은 확인, 출력 후 Queue에 넣어 순서대로 확인
          while(!queue.isEmpty()) {
              int temp = queue.poll();
  
              for(int j = 1; j <= n; j++) {
                  if(check[temp][j] == 1 && checked[j] == false) {
                      queue.offer(j);
                      checked[j] = true;
                      System.out.print(j + " ");
                  }
              }
          }
      }
  
  }
  

  Answer Code2(2023.11.30)

  import java.util.*;
  import java.io.*;
  
  class Main {
      static final int MAX = 1000 + 10;
      static boolean[][] graph;
      static boolean[] visited;
      static ArrayList<Integer> queue; // bfs를 위해 만든 것
      static int N, M, V;
  
      public static void dfs(int idx) {
          visited[idx] = true;
          System.out.print(idx + " "); // 몇 번째 노드를 방문했다.
          
          for(int i = 1; i <= N; i++) {
              if(visited[i] == false && graph[idx][i] == true) {
                  dfs(i);
              }
          }
          
      }
      /*
       * bfs() 풀이 과정
       * 1. queue를 만들고, visited를 새로 초기화해준다.
       * 2. 가장 첫 번째 시작 정점이라는 값(1)을 추가해주고, 그 값(1)을 방문했다라고 표기해준다. (처음 V 값이 1이므로)
       * 3. !queue.isEmpty() 때까지, 가장 앞에 있는 값을 꺼내오고, 출력해 준 다음에 그 값을 기준으로 방문할 수 있는 값들을 방문한다.
       * 
       */
      public static void bfs() {
          queue = new ArrayList<>();
          visited = new boolean[MAX];
  
          queue.add(V);
          visited[V] = true;
  
          while (!queue.isEmpty()) {
              int idx = queue.remove(0); // 가장 앞에 있는 녀석을 꺼내서 걔를 인덱스에 담겠다.
              System.out.print(idx + " ");
  
              for(int i = 1; i <= N; i++) {
                  if(visited[i] == false && graph[idx][i] == true) {
                      queue.add(i);
                      visited[i] = true;
                  }
              }
              
          }
      }
      public static void main(String[] args) throws IOException {
          // 0. 입력 및 초기화
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          StringTokenizer st = new StringTokenizer(br.readLine());
          N = Integer.parseInt(st.nextToken());
          M = Integer.parseInt(st.nextToken());
          V = Integer.parseInt(st.nextToken());
  
          graph = new boolean[MAX][MAX];
          visited = new boolean[MAX];
  
          // 1. graph에 연결 정보 채우기
          for(int i = 0; i < M; i++) {
              st = new StringTokenizer(br.readLine());
              int x = Integer.parseInt(st.nextToken());
              int y = Integer.parseInt(st.nextToken());
              graph[x][y] = true;
              graph[y][x] = true;
          }
  
          // 2. dfs(재귀 함수) 호출 + 출력하기
          dfs(V);
          System.out.println();
  
          // 3. bfs(너비 우선 탐색) 호출 + 출력하기
          bfs();
  
          // 4. 종료
          br.close();
      }
  }
  

  Review

  23.02.15

  • 해당 문제는 dfs, bfs 관련 문제를 처음 풀기 좋은 정석같은 문제였다.

  • 입출력 부분에서 BufferedReader 사용하는 방법을 처음 알게 되었다. 그동안 Scanner를 이용해서 풀었는데, 이번에는 다른 방식으로 풀면서 해당 개념에 대해 배워서 좋았다.

  • dfs, bfs에 대해서는 관련 문제들을 풀면서 개념을 계속적으로 복습해 나가면서, 최종적으로는 머릿속으로도 문제를 풀 수 있는 실력을 갖추도록 하자.

  23.11.15

  • bfs 문제를 풀 때는 queue 자료구조를 사용하고, 관련 메서드 함수들을 기억해두자.

  • 만약 내림차순으로 방문한다라고 가정한다면, dfs 함수에서 for문을 for(int i = N; i >= 1; i--)로 수정해주면 된다. -> 가장 큰 값부터 가장 작은 값까지 방문한다.

  Reference

  • 백준 1260번 DFS와 BFS

  • [백준알고리즘-JAVA]1260번 풀이(DFS와 BFS) - 초보도 이해하는 풀이

  Read All

  ---

• [백준] 2644번. 촌수계산(DFS)

  2023-11-30

  devFancy

  Algorithm
  • 성능 요약
  • 구분
  • Answer Code

  문제 링크

  성능 요약

  • 메모리: 14148 KB, 시간: 120 ms

  구분

  • 그래프 이론(graphs), 그래프 탐색(graph_traversal), 너비 우선 탐색(bfs), 깊이 우선 탐색(dfs)

  Answer Code

  ```java import java.util.; import java.io.;

  class Villages { static final int MAX = 100 + 10; static boolean[][] graph; static boolean visited[]; static int N, M, start, end, answer;

  public static void dfs(int idx, int count) {
      visited[idx] = true;
      if(idx == end) {
          answer = count;
          return;
      }
  
      for(int i = 1; i <= N; i++) {
          if(visited[i] == false && graph[idx][i]) {
              dfs(i, count + 1);
          }
      }
  }
  
  public static void main(String args[]) throws IOException {
      // 0. 입력 및 초기화
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
  
      N = Integer.parseInt(br.readLine());
  
      StringTokenizer st = new StringTokenizer(br.readLine());
      start = Integer.parseInt(st.nextToken());
      end = Integer.parseInt(st.nextToken());
  
      M = Integer.parseInt(br.readLine());
  
      // 1. graph에 연결 정보 채우기
      graph = new boolean[MAX][MAX];
      visited = new boolean[MAX];
      answer = -1;
  

  Read All

  ---

• 알고리즘 수업 - 깊이 우선 탐색 2(DFS)

  2023-11-30

  devFancy

  Algorithm
  • 성능 요약
  • 구분
  • Answer Code(2023.11.30)
  • 문제풀이

  문제 링크

  성능 요약

  • 메모리: 93168 KB, 시간: 1104 ms

  구분

  • 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색

  Answer Code(2023.11.30)

  import java.util.*;
  import java.io.*;
  
  public class DFS_2 {
    static final int MAX = 100000 + 10;
    static ArrayList<Integer>[] graph;
    static boolean[] visited;
    static int N, M, R;
    static int[] answer;
    static int order;
    public static void dfs(int idx) {
      visited[idx] = true;
      answer[idx] = order;
      order++;
  
      for(int i = 0; i < graph[idx].size(); i++) {
        int next = graph[idx].get(i);
        if(visited[next] == false) {
          dfs(next);
        }
      }
    }
    public static void main(String[] args) throws IOException {
      // 0. 입력 및 초기화
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
  
      StringTokenizer st = new StringTokenizer(br.readLine());
      N = Integer.parseInt(st.nextToken());
      M = Integer.parseInt(st.nextToken());
      R = Integer.parseInt(st.nextToken());
  
      // 1. graph에 연결 정보 채우기
      graph = new ArrayList[MAX];
      for(int i = 1; i <= N; i++) {
        graph[i] = new ArrayList<>();
      }
      visited = new boolean[MAX];
      answer = new int[MAX];
      order = 1;
  
      for(int i = 0; i < M; i++) {
        st = new StringTokenizer(br.readLine());
        int u = Integer.parseInt(st.nextToken());
        int v = Integer.parseInt(st.nextToken());
        graph[u].add(v);
        graph[v].add(u);
      }
  
      // 2. 내림차순 정렬
      for(int i = 1; i <= N; i++) {
        Collections.sort(graph[i], Collections.reverseOrder());
      }
  
      // 3. dfs 호출하기
      dfs(R);
  
      // 4. 출력하기
      for(int i = 1; i <= N; i++) {
        bw.write(String.valueOf(answer[i]));
        bw.newLine();
      }
      bw.close();
      br.close();
    }
  }
  
  

  문제풀이

  • 지난번 문제인 깊이 우선 탐색 - 1과 한 가지 다른 점을 제외하고 나머지는 동일하다.

  • 내림차순 정렬을 하기 위해서는 sort()의 인자에 추가로 Collections.reverseOrder() 를 전달해주면 된다.

  

  Read All

  ---

• 알고리즘 수업 - 깊이 우선 탐색 1(DFS)

  2023-11-29

  devFancy

  Algorithm
  • 성능 요약
  • 구분
  • Answer Code(2023.11.29)
  • 문제풀이
    • Step0. 입력 및 초기화
    • Step1. graph에 연결 정보 채우기
    • Step2. dfs(재귀함수 호출)
    • 정리
  • Review

  문제 링크

  성능 요약

  • 메모리: 92592 KB, 시간: 1076 ms

  구분

  • 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색

  Answer Code(2023.11.29)

  import java.util.*;
  import java.io.*;
  
  public class Main {
      static final int MAX = 100000 + 10;
      static ArrayList<Integer>[] graph;
      static boolean[] visited;
      static int N, M, R; // 정점(N)과 간선(M)
      static int[] answer;
      static int order;
      public static void dfs(int idx) {
          visited[idx] = true;
          answer[idx] = order;
          order++;
  
          for(int i = 0; i < graph[idx].size(); i++) {
              int next = graph[idx].get(i);
              if(visited[next] == false) {
                  dfs(graph[idx].get(i));
              }
          }
      }
  
      public static void main(String[] args) throws IOException{
          // 0. 입력 및 초기화
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
  
          StringTokenizer st = new StringTokenizer(br.readLine());
          N = Integer.parseInt(st.nextToken());
          M = Integer.parseInt(st.nextToken());
          R = Integer.parseInt(st.nextToken());
  
          // 1. graph에 연결 정보 채우기
          graph = new ArrayList[MAX];
          for(int i = 1; i <= N; i++) {
              graph[i] = new ArrayList<>();
          }
          visited = new boolean[MAX];
          answer = new int [MAX];
          order = 1;
  
          for(int i = 0; i < M; i++) {
              st = new StringTokenizer(br.readLine());
              int x = Integer.parseInt(st.nextToken());
              int y = Integer.parseInt(st.nextToken());
              graph[x].add(y);
              graph[y].add(x);
          }
  
          // 2. 오름차순 정렬
          for(int i = 1; i <= N; i++) {
              Collections.sort(graph[i]);
          }
  
          // 3. dfs(재귀함수 호출)
          dfs(R);
  
          // 4. 출력
          for(int i = 1; i <= N; i++) {
              bw.write(String.valueOf(answer[i]));
              bw.newLine();
          }
  
          bw.close();
          br.close();
      }
  }
  

  문제풀이

  Step0. 입력 및 초기화

  public class Main {
      static final int MAX = 100000 + 10;
      static ArrayList<Integer>[] graph;
      static boolean[] visited;
      static int N, M, R; // 정점(N)과 간선(M)
      static int[] answer;
      static int order;
  
      public static void main(String[] args) throws IOException {
          // 0. 입력 및 초기화
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
  
          StringTokenizer st = new StringTokenizer(br.readLine());
          N = Integer.parseInt(st.nextToken());
          M = Integer.parseInt(st.nextToken());
          R = Integer.parseInt(st.nextToken());
      }
  }
  

  • N의 최대값이 10만이므로, 2차원 배열로 쓰기에는 저장하기에 크기가 너무 커진다.

  • 그래서 필요할 때마다 쓰는, 동적 할당을 가능하게 해주는 ArrayList을 사용한다.

    • 어떤 특정 노드를 기준으로 봤을 때, 나랑 연결되어 있는 노드가 누가 있는지 는 이전에 배열로 썼던 것과 동일하다.

    • 다만, ArrayList로 만들었기 때문에 M개의 간선 정보에 맞춰서 그때그때마다 하나씩 노드를 추가해가는 구조이다.

  • answer를 하나의 배열 형태로 만들어준 이유는 각각의 노드가 몇번째로 방문했는지 기록하고, 그것을 오름차순으로 출력하기 위해서이다.

  • visited는 이전 바이러스, 연결 요소의 개수 문제와 동일하게, 특정 노드를 방문했는지를 기록하기 위해 boolean 타입의 배열인 자료구조를 사용했다.

  Step1. graph에 연결 정보 채우기

  public class Main {
      static final int MAX = 100000 + 10;
      static ArrayList<Integer>[] graph;
      static boolean[] visited;
      static int N, M, R; // 정점(N)과 간선(M)
      static int[] answer;
      static int order;
  
      public static void main(String[] args) throws IOException {
          // 1. graph에 연결 정보 채우기
          graph = new ArrayList[MAX];
          for (int i = 1; i <= N; i++) {
              graph[i] = new ArrayList<>();
          }
          visited = new boolean[MAX];
          answer = new int[MAX];
          order = 1;
  
          for(int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            graph[x].add(y);
            graph[y].add(x);
          }
      }
  }
  

  • graph[x].add(y)는 x번째 ArrayList 에서 y라는 값을 추가하겠다는 의미이다.

    반대 역시 마찬가지로, graph[y].add(x)은 y번째 ArrayList 에서 x라는 값을 추가하겠다는 의미이다.

  Step2. dfs(재귀함수 호출)

  public class Main {
      static final int MAX = 100000 + 10;
      static ArrayList<Integer>[] graph;
      static boolean[] visited;
      static int N, M, R; // 정점(N)과 간선(M)
      static int[] answer;
      static int order;
  
      public static void dfs(int idx) {
          visited[idx] = true;
          answer[idx] = order;
          order++;
  
          for (int i = 0; i < graph[idx].size(); i++) {
              int next = graph[idx].get(i);
              if (visited[next] == false) {
                  dfs(graph[idx].get(i));
              }
          }
      }
  
      public static void main(String[] args) throws IOException {
          // 2. 오름차순 정렬
          for(int i = 1; i <= N; i++) {
            Collections.sort(graph[i]);
          }
    
          // 3. dfs(재귀함수 호출)
          dfs(R);
      }
  }
  

  • 여기서 order라는 변수는 내가 지금 몇번째인지 순서를 담고 있는 변수이고, 순서를 answer라는 배열에 해당하는 인덱스 번째에 담는 것이다.

    그런 다음에, 1등, 2등, 3등 처럼 순서대로 담길 수 있도록 order에 +1을 증가시켜준다.

  • for(int i = 0; i < graph[idx].size(); i++)은 인덱스번째의 노드랑 연결되어 있는 애들이 이 그래프의 인덱스번째의 ArrayList에 담겨져 있으므로 이 ArrayList를 하나씩 뒤져보겠다는 의미이다.

    예를 들어, 1번째 노드와 연결되어 있는 게 2,4라면 -> 2번 만큼 반복문을 돌리는 것이다.

    그리고 dfs(graph[idx].get(i))은 인덱스와 연결되어 있는 i번째 노드를 가져와서, i를 기준으로 DFS를 태우겠다는 의미이다.

    그런데 조건 없이 불러오면, 무한 루프에 빠질 수 있기 때문에 위에 조건문 if(visited[next] == false) 추가해준다.

    해당 조건문의 의미는 인덱스를 기준으로 i번째 연결되어 있는 요소를 next라는 int형 변수에 담고, 다음 방문하려는 하는 곳이 방문할 기록이 없다면 DFS를 태우겠다는 것이다.

  정리

  

  해당 문제를 풀면서, 아래의 순서에 맞게 생각하고 구현하면 풀 수 있는 문제였다.

  1. DFS, 정점, 간선, 무방향 그래프 -> DFS/BFS

  2. 서로 연결되었다는 정보를 어떻게 하나의 자료구조로 통합할까? -> 2차원 배열 vs ArrayList -> 범위가 크기 때문에 ArrayList 를 사용했다.

  3. 이미 방문한 지점을 다시 방문하지 않으려면 어떤 자료구조를 사용해야 될까?

  4. 어떻게 오름차순으로 방문할 수 있을까?

  5. 방문 순서를 담기 위해서는 어떤 자료구조를 사용해야 될까?

  Review

  • 이전 DFS 유형인 연결 요소의 개수 문제와 다른 점은 크게 2가지 였다.

    • 시작점이 주어진 것(R)이고,

    • N이라는 값이 10만개까지 들어오기 때문에 단순히 2차원 배열로 쓸 수 없어서, 동적 할당을 가능하게 해주는 ArryList를 사용했다.

  • 해당 문제에서 요구했던 건 몇 개를 방문했냐라는 하나의 정수값이 아니라 각각의 노드를 몇 번째로 방문했는지 그걸 알고 싶었기 때문에 이번에는 배열이라는 자료구조를 써야 됐다.

  Read All

  ---

• [solved.ac] Class3++ 2606. 바이러스 (DFS)

  2023-11-28

  devFancy

  Algorithm
  • 성능 요약
  • 구분
  • Answer Code(2023.11.28)

  문제 링크

  성능 요약

  • 메모리: 14236 KB, 시간: 120 ms

  구분

  • 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색

  Answer Code(2023.11.28)

  ```java import java.util.; import java.io.;

  Read All

  ---