[백준1260] DFS와 BFS

 

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

1260번: DFS와 BFS

 

문제설명

단순 DFS, BFS 구현 문제이다!

 

문제 해결 방법

DFS는 스택으로, BFS는 큐로 문제를 풀었다. !

 

코드 구현

package Mar0304;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
import java.util.StringTokenizer;

public class P_1260 {
	public static int N, M, V;
	public static boolean[] visited;
	public static int[][] graph;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		V = Integer.parseInt(st.nextToken());
		
		visited = new boolean[N];
		graph = new int[N][N];
		
		for(int i = 0; i < N; i++) {
			visited[i]=false;
			Arrays.fill(graph[i], 0);
		}
		
		for(int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			graph[a-1][b-1] = 1;
			graph[b-1][a-1] = 1;
		}
		
		DFS(V-1);
		
		Arrays.fill(visited, false);
		System.out.println("");
		BFS(V-1);
		
		
	}
	
	// DFS
	public static void DFS(int start) {
		//visited[start] = true;
		Stack<Integer> stack = new Stack<>();
		stack.push(start);
		
		
		while(!stack.isEmpty()) {
			int current = stack.pop();
			
			if(!visited[current]) {
				System.out.print((current + 1) + " ");
				visited[current] = true;
				
			}
			
			for(int i = N - 1; i >= 0; i--) {
				if(!visited[i]) {
					if(graph[current][i] == 1) {
						stack.push(i);
					}
				}
			}

		}
		
	}
	
	// BFS
	public static void BFS(int start) {
		Queue<Integer> q = new LinkedList<Integer>();
		//visited[start] = true;
		q.offer(start);
		
		while(!q.isEmpty()) {
			int nodeIndex = q.poll();
			
			if(!visited[nodeIndex]) {
				System.out.print((nodeIndex + 1) + " ");
				visited[nodeIndex] = true;
			}
			
			for(int i = 0; i < N; i++) {
				if(graph[nodeIndex][i]==1 && !visited[i]) {
					q.offer(i);
				}
			}
			
		}
		
		
	}
}

 

시간/공간 복잡도

O(N^2)

최적화 및 개선

하지않음

어려웠던 점

문법이 손에 안익어서 어려웠다.