(Baekjoon) dfs,bfs - (1) dfs,bfs

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

1260번: DFS와 BFS

 

 

 

https://sudeky.tistory.com/107

(basic) recursive call,stack,queue, DFS, BFS ....

 

recursive call 을 사용해서 만들었고 솔직히 이해하기란 힘들지만 동영상보고 코딩 조금 하다보면 이해가간다.

linked list, dfs, bfs, queue, stack 의 개념을 파악가능하다면 이해하는데 크게 어렵지 않다.

 

인접행렬의 개념을 사용했으며 인접행렬은

 

0 0 0 1

0 0 1 1

0 1 0 1

1 1 1 0

 

과 같이 파악가능하며 만약에

연결이 되어있다면 1로 표시하고 연결이 되어있지않다면 0으로 표시한다.

(ex, 위의 행렬로 예를들면 2와 3이 연결되어있고 1과 4, 2과 4, 3과 4가 연결되어있다.)

 

위의 그래프를 생각해보면 문제가 무엇을 말하는지 파악가능하다.

그래프는 부모와 자식이 없고 단지 노드와 노드의 연결을 뜻하므로

dfs가 자식노드를 확인한다는것에서 헷갈릴수있지만 자식노드라는말은 편의를 위해서 사용하는것이고

그저 노드의 끝까지 갔다오고 다음 노드의 끝까지 갔다오고 하는 형식으로 파악하면 이해가 가능하다.

bfs는 노드를 주변부터 차근차근 접근하는 형식이다.

 

1) 입력값으로 원,선,시작점이 주어진다.

2) 선들을 연결한다( 인접행렬사용)

3) dfs,bfs을 출력한다.(dfs는 recursive call을 bfs는 queue를 사용)

 

package dfs_bfs;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;


/*
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 
다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 
입력으로 주어지는 간선은 양방향이다.

input : 
4 5 1
1 2
1 3
1 4
2 4
3 4

output: 
1 2 4 3  // dfs
1 2 3 4  // bfs

*/


public class _1260 {
    static int visited[];
    static int xy[][];
    static String imsi[];
    static int N,M,V;

    public static void dfs(int v){
        visited[v] = 1;
        System.out.print(v + " ");
        for (int i = 1; i < N+1; i++) {
            if(visited[i] == 0 && xy[v][i] == 1 ) // 만약에 방문하지 않았고 둘이 연결되어있다면
                dfs(i);		// recursive call 을 사용하여 stack 처럼 쌓는다.
                		   // 출력 -> 그다음 노드탐색 -> 출력 ->  그다음노드 탐색 
                           // 이해가 안간다면 youtube dfs,bfs 참고바람
        }

    }

    public static void bfs(int v){
        Queue<Integer> q = new LinkedList<Integer>();
        q.offer(v);
        visited[v] = 1;
        while(!q.isEmpty()){ // q가 비어질때까지 방문이 모두 종료되면 queue는 비어진다.
            v = q.poll();
            System.out.print(v + " ");
            for (int i = 1; i < N+1; i++) {
                if(visited[i] == 0 && xy[v][i] == 1){ // 만약에 방문하지 않았고 둘이 연결되어있다면
                    q.offer(i); // 값을 queue에다가 집어넣기
                    visited[i] = 1;
                }
            }

        }

    }

    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String a[] = br.readLine().split(" "); // 
        N = Integer.parseInt(a[0]);
        M = Integer.parseInt(a[1]);
        V = Integer.parseInt(a[2]);    

                
        xy = new int[N+1][N+1]; // 전체 점에서 1개씩 더하면된다. 
        						// 문제를 보면은 주어진 정점번호가 1부터 시작하기 때문이다.
        for (int i = 0 ; i < M; i++) {
            imsi = br.readLine().split(" ");
            xy[Integer.parseInt(imsi[0])][Integer.parseInt(imsi[1])] = xy[Integer.parseInt(imsi[1])][Integer.parseInt(imsi[0])] =  1;
        }
        visited = new int[N+1]; // 주어진 정점번호가 1부터 시작하기 때문이다.
        Arrays.fill(visited, 0);
        dfs(V);
        System.out.println();
        Arrays.fill(visited, 0);
        bfs(V);
        

    }



}

 

 

 

 

 

 

 

백준문제풀이Github : 

https://github.com/sdk0213/baekjoon-study

sdk0213/baekjoon-study