DFS와 BFS - 백준(1260, 그래프)

🎯 DFS와 BFS

DFS와 BFS - 1260, 그래프, 실버2

---

🧐 알고리즘[접근방법]

1. 8개의 크로아티아 알파벳 문자를 포함한 배열 선언

2. 입력 받은 문자열에 크로아티아 알파벳 문자가 포함되어 있으면 띄워쓰기(문자열 길이에 포함)으로 변환

3. 문자열 길이를 리턴

---

👨‍💻 소스

package $03_그래프_이론;

import java.util.*;

public class $01_DFS_BFS_1260_실버2 {

	public static void DFS(int[][] map, boolean[] visited, int start) {
		visited[start] = true;
		System.out.print((start + 1) + " ");
		
		for(int i = 0 ; i < map[start].length ; i++) {
			if(map[start][i] == 1 && !visited[i]) {
				DFS(map, visited, i);
			}
		}
	}
	
	public static void BFS(int[][] map, boolean[] visited, int start) {
		Queue<Integer> q = new LinkedList<Integer>();
		q.add(start - 1);
		visited[start - 1] = true;
		
		while(!q.isEmpty()) {
			int k = q.poll();
			System.out.print((k + 1) + " ");
			
			for(int i = 0 ; i < map[k].length ; i++) {
				if(map[k][i] == 1 && !visited[i]) {
					q.add(i);
					visited[i] = true;
				}
			}
		}
	}
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();	// 정점 개수 
		int M = sc.nextInt();	// 간선 개수
		int V = sc.nextInt();	// 정점 시작 번호 

		int[][] map = new int[N][N];
		boolean[] visited = new boolean[N];
				
		for(int i = 0 ; i < M ; i++) {
			int x = sc.nextInt();
			int y = sc.nextInt();
			
			map[x - 1][y - 1] = 1;
			map[y - 1][x - 1] = 1;
		}

		DFS(map, visited, (V - 1));
		Arrays.fill(visited, false); // 방문 배열 초기화
		System.out.println();
		BFS(map, visited, V);
		
		sc.close();
	}
}

---

🏅 결과

---

📖 관련 지식