백준 1260번 ) DFS와 BFS (java)

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

1260번: DFS와 BFS

 

문제

 

 

풀이

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

public class Main {

    static int map[][];
    static boolean[] visit;
    static int n,m,v;

    public static void dfs(int i){
        visit[i] = true;
        System.out.print(i + " ");
        for(int j=1; j<n+1; j++){
            if(map[i][j] == 1 && visit[j]==false) dfs(j);
        }
    }

    public static void bfs(int i){
        Queue<Integer> q = new LinkedList<Integer>();
        q.offer(i);
        visit[i] = true;
        while(!q.isEmpty()){
            int temp = q.poll();
            System.out.print(temp+ " ");

            for(int k=1; k<=n; k++){
                if(map[temp][k] == 1 && visit[k]==false){
                    q.offer(k);
                    visit[k] = true;
                }
            }
        }

    }
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        StringTokenizer st = new StringTokenizer(s, " ");
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        v = Integer.parseInt(st.nextToken());

        map = new int[n+1][n+1];
        visit = new boolean[n+1];

        for(int i=0; i<n+1;i++){
            Arrays.fill(map[i], 0);
        }
        Arrays.fill(visit, false);
        for(int i=0; i<m; i++){
            String edge = br.readLine();
            StringTokenizer st1 = new StringTokenizer(edge, " ");
            int a = Integer.parseInt(st1.nextToken());
            int b = Integer.parseInt(st1.nextToken());
            map[a][b] = 1;
            map[b][a] = 1;
        }

        dfs(v);
        System.out.println();
        Arrays.fill(visit, false);
        bfs(v);
    }
}

BFS는 너비우선, DFS는 깊이 우선.

양방향이므로 양쪽 방향에서 모두 값을 저장해야한다.

 

 

주의할 점

• Queue 구현은 LinkedList로.
  • Queue 사용시, add 와 offer의 차이는 꽉 찼을때 반환 값이 다르다. poll 은 제거하면서 꺼내오기, peek은 값 참조만.
• 인접 리스트로 푸는 경우, 낮은 수 부터 이동해야하므로 정렬을 해야함!
• 정점의 개수가 적은 경우에는 내가 푼것처럼 배열로 풀어도 되지만, 많아지는 경우 효율적이지 못하므로 인접 리스트를 사용하자.