🧑🏻‍💻 문제

💡문제 분석 요약

주어진 그래프를 DFS 와 BFS를 통해 탐색을 한 순서에 대해 출력한다.

---

💡알고리즘 설계

입력받은 그래프와 방문 여부 배열은 static 변수로 선언하여 사용한다.

▶︎ dfs 로직 구현

1. 시작 노드 방문처리
2. for(시작 노드의 자식노드 방문 (값이 존재하고, 방문하지 않은 노드일 경우))
   2-1. 재귀 구현

private static void dfs(int start) {
		check[start] = true;
		sb.append(start + " ");
		
		for (int i = 0; i <= node; i++) {
			if (arr[start][i] == 1 && !check[i]) {
				dfs(i);
			}
		}
		
	}

---

▶︎ bfs 로직 구현

1. 큐에 값 삽입
2. 방문 처리
3. while (큐가 존재하는 동안)
   3-0. start = 큐.poll()
   3-1. for (start의 자식노드 방문 (값이 존재하고, 방문하지 않았을 경우))
   3-2. q.add(자식노드)
   3-3. 자식노드 방문처리

private static void bfs(int start) {
		q.add(start);
		check[start] = true;
		
		while(!q.isEmpty()) {
			start = q.poll();
			sb.append(start + " ");
			
			for (int i = 0; i <=node; i++) {
				if (arr[start][i] == 1 && !check[i]) {
					q.add(i);
					check[i] = true;
				}
			}
		}
	}

---

💡코드

public class Main {

	static StringBuilder sb = new StringBuilder();
	static boolean[] check;
	static int[][] arr;
		
	static int node, line, start;
	static Queue<Integer> q = new LinkedList<>();
	
	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];
		check = new boolean[node+1];
		
		// 간선 노드 그래프 입력
		for (int i = 0; i < line; i++) {
			st = new StringTokenizer(br.readLine());
			
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			arr[a][b] = arr[b][a] = 1;
		}
		
		dfs(start);
		sb.append("\n");
		check = new boolean[node+1];
		
		bfs(start);
		
		System.out.println(sb);
	}
	
	
	// DFS 정의
	private static void dfs(int start) {
		check[start] = true;
		sb.append(start + " ");
		
		for (int i = 0; i <= node; i++) {
			if (arr[start][i] == 1 && !check[i]) {
				dfs(i);
			}
		}
		
	}
	
	// BFS 정의
	private static void bfs(int start) {
		q.add(start);
		check[start] = true;
		
		while(!q.isEmpty()) {
			start = q.poll();
			sb.append(start + " ");
			
			for (int i = 0; i <=node; i++) {
				if (arr[start][i] == 1 && !check[i]) {
					q.add(i);
					check[i] = true;
				}
			}
		}
	}
		
}

💡시간복잡도

• 그래프의 인접 행렬 생성: O(N^2) (N은 노드의 수)
• DFS 함수: O(N^2) (모든 노드와 간선을 순회)
• BFS 함수: O(N^2) (모든 노드와 간선을 순회)

따라서 O(N^2) 의 시간복잡도를 갖는다.

💡 느낀점 or 기억할정보

• BFS & DFS 로직을 구현할 때 방문 여부 배열을 생성하여 활용한다.
• BFS 는 큐를 활용하며, DFS는 재귀함수를 활용한다.