<백준> 1260번 자바 알고리즘 [BFS, DFS]

 

public class Main
{   
    static int n, m, v; // 정점, 간선, 시작점 
    static ArrayList<Integer>[] al;
    static boolean visited[];
    
    
	public static void main(String[] args) throws Exception {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    StringTokenizer stz = new StringTokenizer(br.readLine());
	    n = Integer.parseInt(stz.nextToken());
	    m = Integer.parseInt(stz.nextToken());
	    v = Integer.parseInt(stz.nextToken());
	    
	    al = new ArrayList[n + 1];
	    visited = new boolean[n + 1];
	    
	    // al 초기화
	    for(int i=0; i <= n; i++){
	        al[i] = new ArrayList<>();
	    }
	    // 간선 정보 입력 
	    for(int j=0; j < m; j++){
	        stz = new StringTokenizer(br.readLine());
	        int p1 = Integer.parseInt(stz.nextToken());
	        int p2 = Integer.parseInt(stz.nextToken());
	        al[p1].add(p2);
	        al[p2].add(p1);
	    }
	    
        // 오름차순 정렬 하기 
	    for(int k = 0; k <= n; k++){
	        Collections.sort(al[k]);
	    }
	    
	    
	    dfs(v);
	    visited = new boolean[n + 1];
	    System.out.println();
	    bfs(v);
	    
	    
	    
	}
	private static void dfs(int s) {
	    visited[s] = true;
	    System.out.print(s + " ");
	    for(int tmp : al[s]){
	        if(!visited[tmp]){
	            dfs(tmp);
	        }
	    }
	    
	}
	private static void bfs(int s){
	    Queue<Integer> q = new LinkedList<>();
	    Queue<Integer> ans = new LinkedList<>();
	    visited[s] = true;
	    q.add(s);
	    ans.add(s);
	    while(!q.isEmpty()){
	        int now = q.poll();
	        for( int tmp : al[now]){ // 차례대로 
	            if(!visited[tmp]){ // 만약 방문 안했을 때 
	                q.add(tmp);
	                visited[tmp] = true;
	                ans.add(tmp);
	            }
	        }
	    }
	    
	    while(!ans.isEmpty()){
	        int a = ans.poll();
	        System.out.print(a + " ");
	    }
	    
	}
}

그래프 탐색: 하나의 정점에서 모든 정점을 차례대로 한 번씩 방문하는 것 

모두 이미 방문했으면 이전으로 돌아감 

n m v 
n : 정점 
m : 간선
v : 시작점 

ex) 1 3 => arrList[1] = 3
            arrList[3] = 1
1, 2, 3, 4
al[1] = 2, 3, 4
al[2] = 1, 4
al[3] = 1, 4 
al[4] = 1, 2, 3  

=> sort 안해서 틀렸었었다 문제 잘 읽기! 

 

 

dfs:
1 -> 2 -> 4 -> 3 

bfs:

1 -> 2 -> 3 -> 4

import java.util.*;

public class Main
{   
    
    static final int MAX_N = 1001;
    static int N,M,V;
    static int[][] board = new int[MAX_N][MAX_N];
    static boolean[] visited = new boolean[MAX_N];
    
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt(); M = sc.nextInt();
		V = sc.nextInt();
		
		for(int i = 0; i < M; i++){
		    int a = sc.nextInt();
		    int b = sc.nextInt();
		    board[a][b] = board[b][a] = 1;
		}
		
		dfs(V);
		
	}
	
	static void dfs(int node){
	    visited[node] = true;
	    System.out.print(node + " ");
	    
	    for(int next = 0; next < N + 1; next++){
	        if(!visited[next] && board[node][next] != 0)
	            dfs(next);
	    }
	}
	
	
}

import java.util.*;

public class Main
{
    
    static int N, M, V;
    static Queue<Integer> queue;
    static int[][] board = new int[1001][1001];
    static boolean[] visited;

	public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        V = sc.nextInt();
        
        for(int i = 0; i < M; i++){
            int a = sc.nextInt();
            int b = sc.nextInt();
            board[a][b] = board[b][a] = 1;
        }
        
        bfs(V);
	}
	
	static void bfs(int start){
	    queue = new LinkedList<>();
	    queue.add(start);
	    visited = new boolean[1001];
	    visited[start] = true;
	    System.out.print(start + " ");
	    while(!queue.isEmpty()){
	        int tmp = queue.remove();
	        
	        for(int i = 1; i < N + 1; i++){
	            if(board[tmp][i] == 1 && visited[i] == false){
	                visited[i] = true;
	                queue.add(i);
	                System.out.print(i + " ");
	            }
	        }
	        
	    }
	   
	    
	   
	}
}