[알고리즘] 백준 1260번: DFS, BFS

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

1260번: DFS와 BFS

 

[ 배열의 초기값 ]

int i = new int[3];

이와같이 배열을 만들어 사용할 땐, 따로 값을 지정해주지 않는 이상 default값이 들어가게되는데
int의 경우는 0,
char의 경우는 '0'
String의 경우는 null
boolean의 경우는 false
double의 경우는 0.0
유저가 만든 클래스의 객체 = null

이 들어갑니다.

 

import java.io.*;
import java.util.*;

public class Main{
	
	static int[][] arr;
	static boolean[] check;
	
	static int node, line, start; // node는 정점의 개수
	
	static Queue<Integer> q = new LinkedList<Integer>();
	
	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] = 1;
			arr[b][a] = 1;
			
//			check[i+1] = false; 굳이 초기화 안해도 이미 기본값이 false임
		}
		
		
		dfs(start);
		System.out.println("");
		check = new boolean[node+1];
		bfs(start);
		
	}
	
	public static void dfs(int start) {
		check[start] = true;
		System.out.print(start+" ");
		
		for(int i=1; i<=node; i++) {
			if(arr[start][i] == 1 && !check[i]) {
				dfs(i);
			}
		}
	}
	
	public static void bfs(int start) { 
		
		q.add(start);
		check[start] = true; // 첫번째(start)부터 냅다 큐에 넣는다
		
		while(!q.isEmpty()) { // q가 빌 때까지 반복
			
			start = q.remove(); //반환
			System.out.print(start+" ");
			
			for(int i=1; i<=node; i++) { //넣기
				if(arr[start][i] == 1 && !check[i]) {
					q.add(i);
					check[i] = true;
					}
			}	
		}
	}
}

 

이게 실버라니 ~ 쉽지가 않다 ~