[백준1260] DFS와 BFS

📎 문제링크

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

📄 문제설명

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

입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

📝 문제풀이

백준에서 dfs와 bfs를 경험 해볼수 있는 가장 기초적인 문제라고 생각한다.
이차원배열과 리스트를 이용해 푸는 2가지 방법이 있는데 인접한 간선을 표현하기에는 리스트가 좀더 나은 것 같아 리스트로 구현하였다

💡 Code

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.IOException;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Collections;
public class Main{
	static int N;
	static int M;
	static int V;
	static ArrayList<Integer>adj[];
	static boolean invisited[];
	static StringBuilder sb=new StringBuilder();
	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());
		
		
		adj=new ArrayList[N+1];
		for(int i=1;i<=N;i++) {
			
			adj[i]=new ArrayList<Integer>();
		}
	   
		invisited=new boolean [N+1];
		
		for(int i=0;i<M;i++) {	
		  st=new StringTokenizer(br.readLine());
		  int a=Integer.parseInt(st.nextToken());
		  int b=Integer.parseInt(st.nextToken());
			
		  adj[a].add(b);
		  adj[b].add(a);
			
		}
		 for (int i = 1; i <= N; i++) {
	            Collections.sort(adj[i]);
	        }
		
	DFS(V); 
	sb.append("\n");
	invisited=new boolean[N+1];   //초기화 
	BFS();
	System.out.println(sb);
		
	}
	
	static void DFS(int a) {
	    // 1.체크인 
		invisited[a]=true;
		sb.append(a).append(" ");
		for(int follow:adj[a]) {//2. a점 즉 시작점과 연결된 점들을 순회
			  //방문 할수 있는가? 조건이 무엇인가?
			if(invisited[follow]==false) {//방문 하지 않은 곳만 갈수 있다
				DFS(follow);// 조건이 충족하면 계속 내려가면 된다
			}
		}
		
		
			
	}	  		
		
	static void BFS() {
		Queue<Integer>q=new LinkedList<>();  //BFS는 QUEUE를 만들어 준다
		invisited[V]=true;// 시작점체크인 
		q.add(V); //Q에다 집어넣는다
		
		while(!q.isEmpty()) {
			int temp=q.poll();
			sb.append(temp).append(" ");
		    for(int i:adj[temp]) {//연결된 점 전체를 순회
		    	if(invisited[i]==false) {
		    		invisited[i]=true;  // 방문한곳은 방문확정   		
		    		q.add(i);
		    	}
		    }			
		}		
	}
}

👍 Comment