[BJ1260] DFS와 BFS

백준 알고리즘

🚩 문제 설명

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

1260번: DFS와 BFS

BJ1260

 

⏱️ 시간 복잡도
▪ 그래프의 정점의 개수가 N개라고 한다면, 시간 복잡도는 O(N)에 해당한다.

◾ 그래프가 주어지고 이를 DFS/BFS로 탐색한 결과를 출력하는 문제

◾ 단, 정점 번호가 작은 것을 먼저 방문한다.

 

 

 

---

 

 

 

✅ 입출력

1) N, M, V : 정점의 갯수, 간선의 개수, 탐색을 시작할 정점 번호가 차례대로 주어진다.
2) 간선이 연결하는 두 정점의 번호가 주어진다.
return ➡️ DFS와 BFS로 수행한 결과를 출력한다.

✔️ 예제 1

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

1 2 4 3
1 2 3 4

 

✔️ 예제 2

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

3 1 2 5 4
3 1 4 2 5

 

✔️ 예제

1000 1 1000
999 1000

1000 999
1000 999

 

 

 

---

 

 

 

📑 문제 풀이

with 파이썬 (Python)

import sys
from collections import deque

N, M, V = map(int, sys.stdin.readline().split())  # 정점, 간선, 시작
graph = [[] for _ in range(N + 1)]  # 빈 그래프 선언
visited = [0] * (N + 1)  # visited 배열

# 그래프 생성
for i in range(M):
    n1, n2 = map(int, sys.stdin.readline().split())
    graph[n1].append(n2)
    graph[n2].append(n1)

# 그래프 정렬 - 작은 번호부터 탐색할 수 있도록
for i in range(N + 1):
    graph[i] = sorted(graph[i])


def dfs(v):
    visited[v] = 1
    print(v, end=' ')

    for i in graph[v]:
        if visited[i] == 0:
            dfs(i)


def bfs(v):
    queue = deque([v])
    visited[v] = 1

    while queue:
        n = queue.popleft()
        print(n, end=' ')

        for i in graph[n]:
            if visited[i] == 0:
                queue.append(i)
                visited[i] = 1


dfs(V)
print()
visited = [0] * (N + 1)
bfs(V)

 

with 자바 (Java)

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;


public class BJ1260_DFS와BFS {
	static int N, M, V;
	static List<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
	static boolean[] visited;


	static void dfs(int v) {
		visited[v] = true;
		System.out.print(v + " ");

		for (int g : graph.get(v)) {
			if (!visited[g]) dfs(g);
		}

	} // end dfs


	static void bfs(int v) {
		Queue<Integer> q = new ArrayDeque<>();
		q.offer(v);
		visited[v] = true;

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

			for (int g : graph.get(n)) {
				if (!visited[g]) {
					q.offer(g);
					visited[g] = true;
				}

			}

		}

	} // end bfs


	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("input.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());

		// 인접 리스트 입력 초기화
		for (int i = 0; i < N + 1; i++) {
			graph.add(new ArrayList<Integer>());
		}

		// 인접 리스트 입력
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());

			graph.get(from).add(to);
			graph.get(to).add(from);
		}

		// 인접 리스트 요소 정렬
		for (int i = 0; i < N + 1; i++) {
			Collections.sort(graph.get(i));
		}

		visited = new boolean[N + 1];
		dfs(V);
		System.out.println();

		visited = new boolean[N + 1];
		bfs(V);

	}
}

 

💬 Point

➡️  입력 받은 연결된 두 노드를 인접 리스트 형식으로 만든다.
➡️  dfs, bfs를 수행한다.

◾ 우선 N, M, V 를 입력받는다.

◾ 빈 그래프를 선언하고 두번째 줄 부터 나오는 두 연결된 노드를 이용하여 그래프를 만든다.

◾ 작은 정점부터 탐색하므로 그래프를 오름차순으로 정렬해야 한다.

◾ dfs, bfs를 수행한다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

# 백준 1260 DFS와 BFS 파이썬 python

---