[java] 문제 026 (백준1260)

문제

DFS와 BFS

 

교재 풀이

import java.util.*;
public class P1206_DFS와BFS {
  static boolean visited[];
  static ArrayList<Integer>[] A;
  public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    int N = scan.nextInt(); // 정점의 수
    int M = scan.nextInt(); // 간선의 수
    int Start = scan.nextInt(); // 시작점
    A = new ArrayList[N + 1];
    for (int i = 1; i <= N; i++) {
      A[i] = new ArrayList<Integer>();
    }
    for (int i = 0; i < M; i++) {
      int S = scan.nextInt();
      int E = scan.nextInt();
      A[S].add(E);
      A[E].add(S);
    }
    // 방문할 수 있는 정점이 여러 개인 경우에는 번호가 작은 것을 먼저 방문 하기 위해 정렬
    for (int i = 1; i <= N; i++) {
      Collections.sort(A[i]);
    }
    visited = new boolean[N + 1];  //방문 배열 초기화
    DFS(Start);
    System.out.println();
    visited = new boolean[N + 1];  //방문 배열 초기화
    BFS(Start);
    System.out.println();

  }

  public static void DFS(int node) {  // DFS구현
    System.out.print(node + " ");
    visited[node] = true;
    for (int i : A[node]) {
      if (!visited[i]) {
        DFS(i);
      }
    }
  }

  private static void BFS(int node) {  // BFS구현
    Queue<Integer> queue = new LinkedList<Integer>();
    queue.add(node);
    visited[node] = true;

    while (!queue.isEmpty()) {
      int now_node = queue.poll();
      System.out.print(now_node + " ");
      for (int i : A[now_node]) {
        if (!visited[i]) {
          visited[i] = true;
          queue.add(i);
        }
      }
    }
  }
}

 

내 풀이) 24.6.13에 풀다가 말고 교재 봄. 미완성 

public class Main
{
	public static void main(String[] args) {
		
	}
}

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력
    방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문
     더 이상 방문할 수 있는 점이 없는 경우 종료
    정점 번호는 1번부터 N번까지
첫째 줄에
    정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 
    탐색을 시작할 정점의 번호 V가 주어진다. 
    다음 M개의 줄에는 간선이 연결하는 두 정점의 번호
        양방향이다
        어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다
            특이점있나? 간선이 여러개면 1 2 사이에 간선 여러개 있다고 탐색할 땐
            큰 영향 없을 듯
            아니면 인접리스트로 저장할 때 1과 연결된 노드가 2 2 2 뭐 이런 식으로 될 수있는데 
            뭐 결과 내는 덴 영향 없고, 시간 복잡도 영향만 주지만 
            시간복잡도는 노드+간선 개수인데 대략 10000이고 1000을 곱하면 
            10의 7제곱으로 시간 제한 안에 들어옴
첫째 줄에 DFS를 수행한 결과를
그 다음 줄에는 BFS를 수행한 결과를 출력한다.
V부터 방문된 점을 순서대로 출력하면 된다.

접근법 
    그냥 그동안 해 왔던 dfs, bfs 구현하면 될 듯 
    그냥 원리 구현하는 정도니까 
    dfs는 했으니까 구현 설명은 생략하고
    bfs는 대략 어떻게 할지 보면
        큐를 사용하는데 
        어차피 전반적인 게 dfs와 비슷해서 
        인접리스트, 방문 배열 사용할 것이니까 
슈도코드
    n, m, v 입력: n이 정점 개수, m이 간선 개수 , v가 시작점 
    인접리스트 생성 
        인접리스크 배열 초기화 
        인접리스트 배열을 각각 for문 돌면서 생성해주기 
    visited 배열 초기화 
    
    for m번 반복 
        s, e 받고: s, e는 간선 잇는 노드들 
        a[s].add(e)
        a[e].add(s)
    for n번 반복해서 
        collections.sort로 각 a[i]를 정렬
    
    dfs(v)
    bfs(v)
    

    dfs 구현 ->인수 node 
        if 방문한 노드라면 
            return 
        visited 배열 체크 
        
        for(향상된 포문-> int now: a[node]에 대해 )
            if !visited[now]
                dfs(now)
    bfs 구현 -> 인수 node 
        for 향상된 포문 -> int now: a[node]
            if visited[now]
                continue
            visited[now]=true
            queue.add(node)
            
            while a[nodw]가 빌 때까지
                queue.add()

 

설명

6.13 -> 이 문제 정답을 개념으로 삼고 다른 문제를 푸는 게 시간 아끼는 길이라 생각하여 풀다가 말았음