Baekjoon[1260] - DFS와 BFS

링크

 

1260번: DFS와 BFS

문제설명

• DFS, BFS

문제풀이

• DFS, BFS, 가능한 노드가 여러개일 경우 노드 번호가 작은것 선택 -> 인접행렬 이용하면 됨.

문제코드

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main1260 {

    public static int N;
    public static int M;
    public static int V;
    public static boolean[] d_visit;
    public static int[][] adj;

    public static void DFS(int v) {

        d_visit[v]=true;
        System.out.print(v+" ");
        for (int i = 1; i <= N; i++) {
//            인접행렬에서 연결되어 있고, 방문가능한 경우
//            인접행렬 이용해야 가능한 경우 중 가장 낮은 정점으로 감.
            if(adj[v][i]==1 && !d_visit[i]) {
                DFS(i);
            }
        }
//        모든 경로에 대해서 방문가능한 경로가 없을 경우
        return;
    }




    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("res/Baekjoon/1260.txt"));
        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());
//        인접행렬 양방향
        adj = new int[N+1][N+1];
        int a, b;
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
            adj[a][b] = 1;
            adj[b][a] = 1;
        }

//        DFS
        d_visit = new boolean[N+1];
        DFS(V);
        System.out.println();

//        BFS
        boolean[] b_visit = new boolean[N+1]; 
        LinkedList<Integer> q = new LinkedList<>();
        q.add(V);
        b_visit[V] = true;
        int now;
        while(!q.isEmpty()) {
            now = q.poll();
            System.out.print(now+" ");
            for (int i = 1; i <= N; i++) {
//                인접행렬에서 연결되어 있고, 방문가능한 경우
//                인접행렬 이용해야 가능한 경우 중 가장 낮은 정점으로 감.
                if(adj[now][i]==1 && !b_visit[i]) {
                    q.add(i);
                    b_visit[i]=true;
                }
            }
        }
    }
}

아쉬운점

• 인접행렬말고 간선정보만 이용해서 풀려고 할 때는 노드 번호가 작은순서대로 선택하는게 복잡했었음. 통과 못했었음.
  • 갈수 있는 정점들을 그때그때 정렬했었는데 불필요한 작업이었음 
  • 두 정점 사이에 여러 개의 간선이 있을 수 있다는 조건을 고려했어야 한듯.
• 인접행렬은 1000*1000 중 10000개 간선이라 1%만 사용.
  • 근데 그래도 sort안해도 되서 의미가 있음.
• 고려해야 할 문제조건이 있었다.
  • 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다.
  • 인접행렬 만드는 과정에서 없어짐.
  • 간선 정보를 이용하여 만들 경우에는 중복되는 경우는 배제해야 함.

 

잘한점

• 인접행렬 이용한다는 생각해보니까 바로풀림
  • 양방향을 간선이라 인접행렬이 좋음
• DFS, BFS 구현

 

그래프 개념 및 접근 방법

• 1000*1000 int 배열은 1,000,000*4byte = 4MB라 공간적으로 가능하다.
• 자료구조를 어떻게 선택하여 문제를 풀 지 정해야 한다.
• 정점 중심 관점
  • 인접행렬
  • 인접리스트
• 간선 중심 관점
  • 간선리스트
    • MST
    • 크루스칼
    • 벨만포드