[백준/JAVA] 1260번: DFS와 BFS

🔺 문제

1260번: DFS와 BFS

 

 

🔺 코드

import java.util.*;
import java.io.*;

public class Main {
    static ArrayList<Integer>[] A;  // 인접 리스트
    static boolean[] visited;       // 방문 배열

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

        int N = Integer.parseInt(st.nextToken());   // 정점
        int M = Integer.parseInt(st.nextToken());   // 간선
        int V = Integer.parseInt(st.nextToken());   // 탐색 시작점

        // 인접 리스트 A의 각 ArrayList 초기화
        A = new ArrayList[N + 1];
        for(int i = 1 ; i < N + 1 ; i++) {
            A[i] = new ArrayList<Integer>();
        }

        // 인접 리스트 채우기
        for(int i = 0 ; i < M ; i++) {
            st = new StringTokenizer(br.readLine()," ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            A[a].add(b);
            A[b].add(a);
        }

        // 🔔 번호가 작은 것 먼저 방문하기 위해 정렬 🔔
        for(int i = 1 ; i <= N ; i++) {
            Collections.sort(A[i]);
        }

        visited = new boolean[N + 1];   // 방문 배열 초기화
        DFS(V);
        System.out.println();

        visited = new boolean[N + 1];   // 방문 배열 초기화
        BFS(V);
        System.out.println();
    }

    // DFS 구현 메소드
    static void DFS(int v) {
        System.out.print(v + " ");	    
        visited[v] = true;

        for(int i : A[v]) {
            if(!visited[i]) {
                DFS(i);
            }
        }
    }

    // BFS 구현 메소드
    static void BFS(int v) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(v);
        visited[v] = true;

        while(!queue.isEmpty()) {
            int now = queue.poll();
            System.out.print(now + " ");

            for(int i : A[now]) {
                if(!visited[i]) {
                    visited[i] = true;
                    queue.add(i);
                }
            }
        }
    }
}

✅ 해결 아이디어
✔ DFS & BFS

 

 

💥 유의사항

⇨ 번호가 작은 것 먼저 방문하기 위해 정렬 필요 (Collections.sort(A[i]))

⇨ BFS 수행 전, 방문 배열 visited 초기화 한 번 더

 

---

🔺 다른 풀이들

- 인접 행렬 사용 (정점이 적은 경우 사용)

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

 

 

- 복습용... (상세한 설명....👍👍)

[ 백준 1260 / Java ] DFS와 BFS

---

💬 느낀 점

DFS와 BFS 문제들,,,

이 문제를 시작으로 마스터하겠다,,,,!!!!

 

 

1회독	2회독	3회독	4회독	5회독
V	5.24	6.9	8.17

---

(+6/9 3회독)

import java.util.*;
import java.io.*;
 
public class Main {
    static int N, M, V;
    
    static ArrayList<Integer>[] A;  // 인접 리스트
    static boolean[] visited;       // 방문 배열
    static StringBuilder sb1 = new StringBuilder();
    static StringBuilder sb2 = new StringBuilder();
    
    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());
        V = Integer.parseInt(st.nextToken());
        
        A = new ArrayList[N + 1];
        for(int i = 1 ; i <= N ; i++) {
            A[i] = new ArrayList<>();
        }
        
        while(M --> 0) {
            st = new StringTokenizer(br.readLine(), " ");
            
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            
            A[s].add(e);
            A[e].add(s);
        }
        
        for(int i = 1 ; i<= N ; i++) {
            Collections.sort(A[i]);
        }
        
        visited = new boolean[N + 1];
        dfs(V);
        System.out.println(sb1);
        
        visited = new boolean[N + 1];
        bfs(V);
        System.out.println(sb2);
    }
    
    private static void dfs(int v) {
        sb1.append(v).append(" ");
        visited[v] = true;
        
        for(int n : A[v]) {
            if(!visited[n]) {
                dfs(n);
            }
        }
    }
    
    private static void bfs(int v) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(v);
        visited[v] = true;
        
        while(!queue.isEmpty()) {
            int now = queue.poll();
            sb2.append(now).append(" ");
            
            for(int n : A[now]) {
                if(!visited[n]) {
                    visited[n] = true;
                    queue.add(n);
                }
            }            
        }
    }
}