솜이의 데브로그

백준 1260번 ) DFS와 BFS (java) 본문

Algorithm/백준

백준 1260번 ) DFS와 BFS (java)

somsoming 2022. 3. 9. 02:17

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

 

1260번: DFS와 BFS

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사

www.acmicpc.net

 

문제

 

 

풀이

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은 값 참조만.
  • 인접 리스트로 푸는 경우, 낮은 수 부터 이동해야하므로 정렬을 해야함!
  • 정점의 개수가 적은 경우에는 내가 푼것처럼 배열로 풀어도 되지만, 많아지는 경우 효율적이지 못하므로 인접 리스트를 사용하자.