[백준] 1260번 DFS & BFS JAVA (자바) 풀이

문제 1260번

 :  그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램

 :  방문할 수 있는 정점이 여러 개인 경우 정점 번호가 작은 것부터 방문

 :  더 이상 방문할 수 있는 점이 없을 때 종료
 :  정점 번호는 1 ~ N

 

 

 

 [입력]

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

 :  둘째 줄부터 간선이 연결하는 두 정점의 번호

    (정점 사이에 여러 개의 간선이 있을 수 있고 입력으로 주어지는 간선은 양방향)

 

 

 [출력]

 :   V부터 방문된 점을 순서대로 출력

 

 

 [설명]

 

  - DFS  

 

 현재 정점에서 갈 수 있는 점들까지 들어가면서 탐색

 Stack 혹은 재귀함수로 구현

 

• 경로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가
  더 이상 갈 수 없게되면 다른 방향으로 다시 탐색 진행
• 모든 노드를 방문하는 경우에 사용

 

 

  - BFS

 

 

 현재 정점에 연결된 가까운 점들부터 탐색

 

 Queue를 사용해서 구현

 

 

 

 [코드]

import java.io.*;
import java.util.*;
public class Main{
    static int[][] arr;
    static boolean[] visit;
    static int x, y, N;
    static Queue<Integer> q = new LinkedList<>();
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        st= new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int V = Integer.parseInt(st.nextToken());
        
        arr = new int[N+1][N+1];
        visit = new boolean[N+1];
        
        for(int i =0; i<M; i++){
            
            st= new StringTokenizer(br.readLine());
            x = Integer.parseInt(st.nextToken());
            y = Integer.parseInt(st.nextToken());
            arr[x][y] = arr[y][x] = 1;
        }
        
        DFS(V);
        System.out.println();
         visit = new boolean[N + 1];
        BFS(V);
    }
    
    public static void DFS(int node){
        visit[node]=true;
        System.out.print(node + " ");
        for(int i =1; i< N+1; i++){
            if(arr[node][i]==1 && visit[i] == false){
                DFS(i);
            }
        }
    }
    
    public static void BFS(int node){
        q.add(node);
        visit[node]=true;

        while(!q.isEmpty()) {
            
            node= q.poll();
			
		
            System.out.print(node + " ");
            
            for(int i = 1; i<N+1; i++){
                if(arr[node][i] == 1 && visit[i]==false) {
					q.add(i);
					visit[i] = true;
                }
            }
        }
    }
}

 

 [해설]
     

 :  static int[][] arr;  2차원 배열 설정

    static boolean[] visit;  방문기록 설정

    static int x, y;  둘째줄부터 입력되는 x, y

    static int N;  첫째줄 입력 N (main, DFS, BFS에 모두 쓸거라 앞으로 뺌)

    static Queue<Integer> q = new LinkedList<>(); BFS에서 사용

 

 :  st = new StringTokenizer(br.readLine());  한 줄 입력보기
    N = Integer.parseInt(br.readLine());  노드 개수 (첫째 줄 입력)

    int M = Integer.parseInt(st.nextToken());  연결선 개수 (첫째 줄 입력)
    int V = Integer.parseInt(st.nextToken());  시작노드 (첫째 줄 입력)

 

 :  arr = new int[n+1][n+1];  배열 1부터 보려고 + 1 하기

    visit = new boolean[n+1];  배열 1부터 보려고 +1 하기

 :  for(int i=0; i<M; i++) {  쌍을 이루는 개수만큼만 계산

          st = new StringTokenizer(br.readLine());  단어 끊어 읽기

          int x = Integer.parseInt(st.nextToken());  연결 노드 (둘째 줄부터)

          int y = Integer.parseInt(st.nextToken());  연결 노드 (둘째 줄부터)

          arr[x][y] = arr[y][x] = 1;   입력받은 값들 1로 처리 (arr[1][2] = arr[2][1]) 
    }                                          

 :  DFS(V);  dfs에 V 넣고 시작 (시작 노드 고정하고 계산)

    System.out.println(); 

 

:   visit = new boolean[N+1];  bfs에서도 visit 쓸거라 새롭게 지정
                                              안그러면 dfs에서 사용된 값들이 누적된다

 

    BFS(V);  bfs에 V 넣고 시작 (시작 노드 고정하고 계산)
 

:  public static void DFS(int node) {  node 현재 비교값
         visit[node] = true;  현재의 노드를 방문 처리 ( V = node 로 초기값 고정) 

         System.out.print(node+ " ");  노드로 지정될 때마다 출력

         for(int i=1; i<N+1; i++) {  
                  if(arr[node][i] == 1 && visit[i] == false) {  node와 연결됐지만 방문 기록은 false

                           DFS(i, count+1);                            현 node는  V이다

                  }                                                              방문기록이 없는 다른 노드들로 새롭게 갱신

         }

   }   

 

:  public static void BFS(int node) {  node 현재 비교값

         q.add(node);  노드들 큐에 삽입
         visit[node] = true;  현재의 노드를 방문 처리 ( V = node 로 초기값 고정) 

         

         while(!q.isEmpty()) {

                  node = q.poll(); 큐가 빌 때까지 큐에서 뺀 것들 node에 저장

                                           큐에 초기값 node = V 넣었으니까 바로 빼고 밑에 코드 실행

                                           밑에서 q.add(i) 로 넘어오는 노드들 다 빼서 node에 저장

 

                  System.out.print(node+ " "); 노드 출력

 

                  for(int i=1; i<N+1; i++) {  
                           if(arr[node][i] == 1 && visit[i] == false) {  node 연결O, 방문기록 false

                                    q.add(i);                                         해당 i 큐에 넣기  

                           }        visit[i] = true;                                  방문처리

                  }

    }   

 

 

 [문제 과정]

 

출처&nbsp;https://velog.io/@youswim96

    

총 노드	5
시작 노드	3
연결 노드	5 - 4 5 - 2 1 - 2 3 - 4 3 - 1

 

DFS
	방문처리 완료	다음 경로확인	DFS	출력
1 단계	visit[3]	arr[3][1]	DFS(3)	3
2 단계	visit[1]	arr[1][2]	DFS(1)	1
3 단계	visit[2]	arr[2][5]	DFS(2)	2
4 단계	visit[5]	arr[5][4]	DFS(5)	5
5 단계	visit[4]	-	DFS(4)	4

 

BFS
	계산	q.add	q.poll	방문완료 / 출력
1 단계	초기값 3부터 시작	3	3	3
2 단계	3이랑 연결된 노드 찾기	1, 4	1, 4	1, 4
3 단계	1이랑 연결된 노드 찾기	2	2	2
4 단계	4랑 연결된 노드 찾기	5	5	5

      

이제 풀어보러 갈께요 :)

 

 

 

 

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

1260번: DFS와 BFS

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *