알고리즘 - DFS와 BFS

문제

• 링크

• 추천 문제 : 링크

코드

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

public class BOJ_1260 {
	static int N,M,V,val;
	static int[][] arr; 
	static boolean[] visited;
	static int[] answer;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stk = new StringTokenizer(br.readLine());
		N = Integer.parseInt(stk.nextToken());
		M = Integer.parseInt(stk.nextToken());
		V = Integer.parseInt(stk.nextToken());
		arr = new int[N][N];
		visited = new boolean[N];
		answer = new int[N];
		for(int i = 0; i < M ; i++) {
			StringTokenizer stk1 = new StringTokenizer(br.readLine());
			int start = Integer.parseInt(stk1.nextToken());
			int end = Integer.parseInt(stk1.nextToken());
			arr[start-1][end-1] = 1;
			arr[end-1][start-1] = 1;
		}
		dfs(V-1);
		StringBuffer stb = new StringBuffer();
		for(int i = 0; i < answer.length ; i++) {
			if(answer[i] != 0)
				stb.append(answer[i] + " ");				
			
		}
		//
		//System.out.println(Arrays.toString(answer));
		stb.setLength(stb.length()-1);
		System.out.println(stb);
		visited = new boolean[N];
		answer = new int[N];
		bfs();
		stb = new StringBuffer();
		for(int i = 0; i < answer.length ; i++) {
			if(answer[i] != 0)
				stb.append(answer[i] + " ");				
		}
		
		stb.setLength(stb.length()-1);
		System.out.println(stb);
		
	
		
	}
	private static void bfs() {
		// TODO Auto-generated method stub
		Queue<Integer> queue = new LinkedList<>();
		visited[V-1] = true;
		queue.offer(V-1);
		int val = 0;
		while(!queue.isEmpty()) {
			int poll = queue.poll();
			answer[val++] = (poll+1);
			for(int i = 0; i < N ;i++) {
				if(arr[poll][i]==1 && !visited[i]) {
					visited[i] = true;
					queue.add(i);
				}
			}
		}
	}
	
	private static void dfs(int start) {
		// TODO Auto-generated method stub
		if(visited[start])
		{
			return;
		}
		visited[start] = true;
		answer[val] = start+1;
		val = val+1;
		for(int i = 0; i < N; i++) {
			if(!visited[i] && arr[start][i] == 1) {
				dfs(i);
			}
		}
		
	}
}

회고

• 역시 꾸준히 안 하면 계속 잃어버리는 것이 있는 듯 ㅠㅠ

• 풀었던 문제들도 계속해서 반복해야 한다

• Java에 익숙해져야 한다는 것이 중요