[BOJ 1260] DFS와 BFS (java)

문제 링크 https://www.acmicpc.net/problem/1260

문제풀이

package basics_600;

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 BOJ1260 {
	static boolean[] visited;
	static int node;
	static int edge;
	static int start;
	static int[][] linked;

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		// 노드 수
		node = Integer.parseInt(st.nextToken());
		// 간선 수
		edge = Integer.parseInt(st.nextToken());
		// 시작 번호
		start = Integer.parseInt(st.nextToken());

		// 해당 노드가 방문했는지 여부
		visited = new boolean[10001];
		// 간선
		linked = new int[1001][1001];

		// 간선 표시
		for (int i = 1; i <= edge; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			linked[a][b] = linked[b][a] = 1;
		}

		dfs(start);
		clear();
		bfs(start);

	}

	static void dfs(int num) {
		// 방문했으니까 true
		visited[num] = true;
		System.out.print(num + " ");
		// 노드 num과 연결되어 있으면서, 방문하지 않은 노드이면 dfs 수행
		for (int j = 1; j <= node; j++) {
			if (linked[num][j] == 1 && !visited[j]) {
				dfs(j);
			}
		}
	}

	static void clear() {
		for (int i = 0; i < visited.length; i++) {
			visited[i] = false;
		}
		System.out.println();
	}

	static void bfs(int num) {
		//방문했으니까 true 
		visited[num] = true;
		System.out.print(num + " ");

		//방문한 노드 queue 에 넣어주기 
		Queue<Integer> queue = new LinkedList<>();
		queue.offer(num); // add -> 예외발생 / offer -> 값 리턴

		//queue가 다 비워질때까지(모든노드 방문) 
		while (!queue.isEmpty()) {
			int temp = queue.poll(); // queue.poll을 바로 인덱스에 넣어주면 에러남 ! 
			for (int j = 0; j <= node; j++) {
				// 노드 num과 연결되어 있으면서, 방문하지 않은 노드이면 bfs 수행
				if (linked[temp][j] == 1 && !visited[j]) {
					visited[j] = true;
					queue.offer(j);
					System.out.print(j + " ");

				}
			}
		}
	}

}