백준 1260

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

1260번: DFS와 BFS

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

public class Main {

	static StringBuilder sb = new StringBuilder(); //출력을 위한 sb
	static boolean[] check;  //체크
	static int[][] arr;  //인접 노드를 표시하기 위한 2차원배열
	
	static int node, line, start;
	
	static Queue<Integer> q = new LinkedList<>();  //bfs를 위한 q

	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 ++) {
			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;	//인접노드면 1 인접하지 않은 노드면 0
		}
			//sb.append("\n");
			dfs(start);
			sb.append("\n");
			check = new boolean[node+1];
			
			bfs(start);
			
			System.out.println(sb);
		
		}
	public 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);  //그 노드를 다음 레벨에 넣어준다
		}
		
	}
	
	public static void bfs(int start) {
		q.add(start);
		check[start] = true;  //방문
		
		while(!q.isEmpty()) {
			
			start = q.poll();
			sb.append(start + " ");
			
			for(int i = 1 ; i <= node ; i++) {
				if(arr[start][i] == 1 && !check[i]) {
					q.add(i);
					check[i] = true;
				}
			}
		}
		
		
	}

}

bfs는 q를 사용할것

 

서로 인접하는 노드를 확인하기 위해 arr = new int[node+1][node+1]의 2차원 배열 생성

DFS BFS 참고강의

https://www.youtube.com/watch?v=_hxFgg7TLZQ