DFS와 BFS(1260번)

• 티어 : Sliver 2
• 정답여부 : 정답
• 알고리즘 유형 : 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색
• 시간 제한 : 2초

💡문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

💡입력

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

💡출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

💡예제 입력 1

4 5 1
1 2
1 3
1 4
2 4
3 4

💡예제 출력 1

1 2 4 3
1 2 3 4

💡예제 입력 2

5 5 3
5 4
5 2
1 2
3 4
3 1

💡예제 출력 2

3 1 2 5 4
3 1 4 2 5

💡예제 입력 3

1000 1 1000
999 1000

💡예제 출력 3

1000 999
1000 999

💡문제요약

주어진 수로 DFS와 BFS 알고르짐을 구현하면 되는 문제

💡알고리즘 설계

• StringBuilder sb: 결과를 저장하기 위한 StringBuilder 객체
• Queue<Integer> que: BFS에서 사용할 큐
• boolean[] visit: 노드 방문 여부를 저장하기 위한 배열
• int node, line, start: 노드 개수, 간선 개수, 시작 노드 번호를 저장하는 변수
• int[][] arr: 인접 행렬을 나타내는 2차원 배열

1. 주어진 정점, 간선 시작 을 입력받는다.
2. 인접 행렬을 사용하여 그래프를 표현한다. 노드 간의 연결 여부를 나타내는 arr 배열에 값을 저장
3. DFS
   1. • 시작 노드를 받아 노드를 방문했으면 표시한다.
   2. 인접한 노드 중 방문하지 않는 노드가 있으면 해당 노드로 재귀적으로 dfs 함수를 호출한다.
4. BFS 호출 전 visit를 초기화 해준다.
5. BFS
   1. start받아 큐에 넣고 방문했다고 표시
   2. 큐가 빌 때까지 반복하여 큐에서 노드를 하나씩 꺼내고 sb에 추가한다. 해당 노드와 연결된 미방문 노드들을 큐에 넣고 방문했다고 표시

💡작성코드

• Java

import java.io.*;
import java.util.*;
public class Main{
	static StringBuilder sb = new StringBuilder();
	static Queue<Integer>que = new LinkedList<>();
	static boolean[] visit;
	static int node , line, start;
	static int[][] arr;	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		 node = Integer.parseInt(st.nextToken());
		 line = Integer.parseInt(st.nextToken());
		 start = Integer.parseInt(st.nextToken());
		arr = new int[node + 1][node +1];
		visit = new boolean[node + 1];
		for (int i = 0; i< line; i++) {
		StringTokenizer str = new StringTokenizer(br.readLine());
		int a = Integer.parseInt(str.nextToken());
		int b = Integer.parseInt(str.nextToken());
		arr[a][b] = arr[b][a] =  1;
		}
		dfs(start);
		sb.append("\n");
		visit = new boolean[node + 1];
		bfs(start);
		System.out.println(sb)		
			}
	public static void dfs(int start) {
		visit[start] = true; // 노드 중복 접근 방지를 위한 방문 체크 배열(boolean)
		sb.append(start + " "); // 방문했으면 sb 추가
		for (int i = 1; i <= node; i++) { // i 는 dfs 배열의 새로운 분기를 뜻함
			if (arr[start][i] == 1 && visit[i] == false) {
				dfs(i);
			}
		}
	}
	public static void bfs(int start) {
		que.offer(start);
		visit[start] = true;
		while(!que.isEmpty()) {
			int temp = que.poll();
			sb.append(temp + " ");
			for(int i = 1; i < node+1; i++) {
				if(arr[temp][i] == 1 && visit[i]==false) {
					que.offer(i);
					visit[i] = true;
				}
			}
		}	
	}	
}

💡시간복잡도

O(V + E) V : vertex 개수, E : edge 개수

💡틀린 이유 or 수정할 부분

틀린건 없어 다른 분의 풀이 코드를 가져왔다.

💡틀린 부분 수정 or 다른풀이

• Java

import java.util.*;
public class dfs와bfs {
    static int n,m,v,s,e;
    static ArrayList<Integer>[] A;
    static boolean[] visited;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt(); // 노드 개수
        m = sc.nextInt(); // 간선 개수
        v = sc.nextInt(); // 시작점
        A = new ArrayList[n+1];
        for (int i=1; i<=n; i++){ // 그래프 정보 개수
            A[i] = new ArrayList<Integer>();
        }
        for (int i=1; i<=m; i++){
            s = sc.nextInt(); // 노드간의 시작점
            e = sc.nextInt(); // 노드간의 끝점
            A[s].add(e); // 시작점-끝점 이어주기
            A[e].add(s); // 끝점-시작점 이어주기
            /*System.out.println("A["+s+"] : " + A[s]);
            System.out.println("A["+e+"] : " + A[e]);*/
        }
        for (int i=1; i<=n; i++){
            Collections.sort(A[i]);
        } // 정점 번호가 작은 것을 먼저 방문
        visited = new boolean[n+1]; // 노드를 visited[1]부터 넣기 위해 n+1로 선언
        dfs(v);
        System.out.println();
        visited = new boolean[n+1];
        bfs(v);
        System.out.println();
        }
        public static void dfs(int node){
            System.out.print(node +" ");
            visited[node] = true; // 방문
            for (int i : A[node]){ // A 배열에 담긴 개수만큼 반복
                if(!visited[i]){ // A 배열에 담긴 숫자중에 방문하지 않은 게 있다면
                    dfs(i);
                }
            }
        }
        public static void bfs(int node){
            Queue<Integer> q = new LinkedList<>(); // 큐 생성
            q.add(node); // 큐에 노드를 넣어준다
            visited[node] = true; // 방문
            while(!q.isEmpty()){ // 큐가 비어있을때까지 반복
                int now_node = q.poll(); // 맨 앞 큐 값을 밀어내기
                System.out.print(now_node + " "); // 그거 출력
                for (int i:A[now_node]){
                    if(!visited[i]){
                        visited[i] = true;
                        q.add(i);
                    }
                }
            }
        }
}

💡느낀점 or 기억할 정보

역시 DFS 와 BFS는 솔직히 코드를 외우고 구현을 했다. 어느정도 코드 공식을 외우는 것도 도움이 되는거 같다.