[백준 | Java] 1260번 DFS와 BFS

1260번 / DFS와 BFS

❓ DFS와 BFS

🏷️ 관련 주제 : Graph DFS BFS

💦 나의 시도

Try

1. 입력받은 두 정점 dot1, dot2에 대하여 int형 이차원 배열 graph[dot1 - 1][dot2 - 1], graph[dot2 - 1][dot1 - 1]에 1을 할당
   • 전체 배열을 탐색하려면 오래 걸릴 것 같아서 int[] minNum의 인덱스 i에 정점 i + 1에 연결된 최소 정점의 값을 할당
2. DFS 실행
   • 지나간 정점을 체크하기 위해 ArrayList visited를 사용
   • 정점을 지날 때, visited에 해당 정점의 값을 추가
3. BFS 실행
   • 큐(Queue)를 사용
   • 큐에 시작할 정점을 추가 후, BFS 탐색 시작
   • 큐에서 원소를 꺼내 해당 정점에 간선이 연결된 정점을 조회
     • 큐에서 꺼낸 원소는 visited에 추가
   • 연결된 정점이 visited에 추가되어 있지 않으면 큐에 해당 정점을 추가

모든 정점을 다 지나갔는지 체크하는 부분에서 고민하다가 시간 초과가 되었는데
인터넷에서 풀이를 찾아보고 비교해 보니
풀이가 상당히 비슷하게 작성된 느낌이었다.
조금 더 공부한다면 다음에는 맞출 수 있을 것 같다는 느낌이 들었다.
틀렸지만 알고리즘 및 구현을 좀 더 공부해서 다음에는 맞출 수 있도록 해야겠다.
풀이는 참고한 블로그에서 내가 쓴 코드와 비교하여 아주 약간만 수정하였다.
(변수 이름 및 배열 길이 정도...)

⏱️ Time Over!

[백준알고리즘-JAVA]1260번 풀이(DFS와 BFS) - 초보도 이해하는 풀이
이 블로그를 참고하여 코드를 다시 작성하였습니다.

맞았습니다!!

• 메모리 : 23948 KB
• 시간 : 256 ms
• 코드 길이 : 1887 B

📑제출 기록 및 오답 원인

 

💯 해결 방법

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

public class Main {
    static StringBuilder sb = new StringBuilder();
    static boolean[] check;
    static int[][] graph;
    static int N, M, V;
    static Queue<Integer> q = new LinkedList<>();

    public static void main(String[] args) throws Exception {
        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 int[N][N];
        check = new boolean[N];

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int dot1 = Integer.parseInt(st.nextToken());
            int dot2 = Integer.parseInt(st.nextToken());

            graph[dot1 - 1][dot2 - 1] = graph[dot2 - 1][dot1 - 1] = 1;
        }

        dfs(V);
        sb.append("\n");

        check = new boolean[N];
        bfs(V);
        System.out.println(sb);


    }

    public static void dfs(int start) {
        check[start - 1] = true;
        sb.append(start + " ");

        for (int i = 0; i < N; i++) {
            if (graph[start - 1][i] == 1 && !check[i]) {
                dfs(i + 1);
            }
        }
    }

    public static void bfs(int start) {
        q.offer(start);
        check[start - 1] = true;

        while (!q.isEmpty()) {
            start = q.poll();
            sb.append(start + " ");

            for (int i = 0; i < N; i++) {
                if (graph[start - 1][i] == 1 && !check[i]) {
                    q.offer(i + 1);
                    check[i] = true;
                }
            }
        }
    }
}

 

🏷️ 문제 풀면서 참고한 블로그

• [백준알고리즘-JAVA]1260번 풀이(DFS와 BFS) - 초보도 이해하는 풀이
• [알고리즘] 너비 우선 탐색(BFS)이란