99클럽 코테 스터디 39일차 TIL + DFS, BFS

백준

https://www.acmicpc.net/problem/1260

 

---

- 오늘의 학습 키워드 : DFS, BFS

- 공부한 내용 본인의 언어로 정리하기

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

public class Main {

    static int N, M;
    static int[][] node;
    static boolean[] visitedDFS;
    static boolean[] visitedBFS;

    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());
      int V = Integer.parseInt(st.nextToken());

      node = new int[N+1][N+1];
      visitedDFS = new boolean[N+1];
      visitedBFS = new boolean[N+1];
      for (int i=0; i<M; i++) {
        st = new StringTokenizer(br.readLine());
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());

        //간선 연결
        node[a][b] = node[b][a] = 1;
      }
      dfs(V);
      System.out.println();
      bfs(V);
    }

    private static void dfs(int V) {
      visitedDFS[V] = true; //노드 방문
      System.out.print(V + " "); //방문한 노드 출력

      //인접 노드 순회
      for (int i=1; i<=N; i++) {
        //방문한 적 없고 1인 경우
        if (!visitedDFS[i] && node[V][i] != 0) {
          dfs(i);
        }
      }
    }

    private static void bfs(int V) {
      Queue<Integer> queue = new LinkedList<>();
      queue.offer(V); //시작점
      visitedBFS[V] = true; //노드 방문
      System.out.print(V + " "); //방문한 노드 출력

      //queue가 빌 때까지 반복
      while(!queue.isEmpty()) {
        int tmp = queue.poll();

        //인접 노드 순회
        for (int i=1; i<=N; i++) {
          //방문한 적 없고 1인 경우
          if(!visitedBFS[i] && node[tmp][i] != 0) {
            queue.offer(i); //큐에 삽입
            visitedBFS[i] = true; //노드 방문
            System.out.print(i + " "); //방문한 노드 출력
          }
        }
      }
    }
}

- 오늘의 회고 : DFS(stack/연결리스트/인접행렬), BFS(queue)

방문 노드 확인 필요하고, stack/queue인 경우는 각 stack, queue가 비어있을 때까지 진행한다.

---

99클럽 1기를 수강하면서 작성한 글입니다.

https://99club.oopy.io/

99클럽-1기 모집 중