백준 1260: BFS/DFS 풀이

문제

• 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성
• 단, 방문할 수있는 정점이 여러개인 경우에는 정점 번화가 작은것을 먼저 방문하고 , 더 이상 방문할수 있는 점이 없는 경우 종료
• 정점 번호는 1번부터 N번까지

---

입력

첫째줄에  정점의 개수: N , 간선의 개수 : M,   탐색을 시작할 정점의 번호: V  

다음 M개의 줄에는 간선이 연결하는 두 정점의 번화가 주어진다.

어떤 두 정점 사이에 여러개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

---

출력

• 첫째 줄에는 DFS를 수행한 결과를
• 다음 줄에는 BFS를 수행한 결과를 출력
• V부터 방문된 점을 순서대로 출력하면 된다.

---

---

package Baek;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class DFSBFS1260 {
final static int MAX= 1000+10;
static boolean graph[][];   // 그래프
static boolean visited[];   // 해당 노드를 방문했는지 대한 체크
static ArrayList<Integer> queue;  // BFS를 풀기위해서 만든 QUEUE
static int N, M, V ;  // 정점의 개수: N , 간선의 개수 : M,   탐색을 시작할 정점의 번호: V
//===============================================================================
static void dfs(int idx){   //idx--> 현재 노드의 인덱스
  System.out.print(idx+" ");
  visited[idx]=true;        //현재 노드를 방문했으므로 true로 체크합니다.
  for (int i=1;i<=N;i++){    //현재 노드와 연결된 노드를 찾기 위한 반복문
    if(!visited[i]&& graph[idx][i]){ // i 노드를 방문하지 않았고, idx와 i가 연결되어있는 경우를 i를  다음노드로 선택하고
      dfs(i);                        //재귀호출
    }
  }
}
//==========================================================

static void bfs( ){
  queue = new ArrayList<>();    //시작 노드를 큐에 추가하고 방문한것으로 체크합니다.
  visited = new boolean[MAX];
  queue.add(V);
  visited[V]=true;

  while (!queue.isEmpty()){  // 큐가 빌때 까지 반복
    int idx= queue.remove(0); //큐에서 노드를 하나 꺼내옵니다.
    System.out.print(idx+" ");
    for (int i=1;i<=N;i++){   //현재 노드와 연결된 노드를 찾기 위한 반복문
      if (!visited[i]&& graph[idx][i]){ //i 노드를 방문하지 않았고, idx와 i가 연결되어있는 경우, i를 큐에 추가하고 방문한것으로 체크
        visited[i]=true;
        queue.add(i);
      }
    }
  }
}
//=======================================================

  public static void main(String[] args) throws IOException {
    BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st= new StringTokenizer(br.readLine());
    N=Integer.parseInt(st.nextToken());
    M=Integer.parseInt(st.nextToken());
    V=Integer.parseInt(st.nextToken());

    graph= new boolean[MAX][MAX];   //그래프 배열을 초기화
    visited= new boolean[MAX];       //visited 배열을 초기화

    for (int i=0; i<M;i++){    //간선 정보를 입력받아 인접행렬을 만듬
      st= new StringTokenizer(br.readLine(), " ");
      int x= Integer.parseInt(st.nextToken());
      int y= Integer.parseInt(st.nextToken());
      graph[x][y]=graph[y][x]=true;   //graph[x][y]  -->graph[y][x] true로 바꾸어 양방향 그래프를 표현

    }
    dfs(V);
    System.out.println();
    bfs();
  }

}