[문제] 백준 1260번 BFS와 DFS

* 출처

www.acmicpc.net/problem/1260

1260번: DFS와 BFS

 

내 풀이 (1)

인접리스트를 이용해서 그래프를 표현했다.

 

public class BOJ_1260 {
	static int N;
	static ArrayList<ArrayList<Integer>> list;
	static boolean[] visited;
	static StringBuilder sdfs = new StringBuilder();
	static StringBuilder sbfs = new StringBuilder();
	
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine()," ");
		
		N = Integer.parseInt(st.nextToken());	// 정점 개수
		int M = Integer.parseInt(st.nextToken());	// 간선 개수
		int V = Integer.parseInt(st.nextToken());	// 탐색 시작 정점 번호
		
		list = new ArrayList<>();
		for(int i=0;i<N+1;i++) {	// 1 based 
			list.add(new ArrayList<>());
		}
		
		for(int i=0;i<M;i++) {
			st = new StringTokenizer(in.readLine()," ");
			int p1 = Integer.parseInt(st.nextToken());
			int p2 = Integer.parseInt(st.nextToken());
			list.get(p1).add(p2);
			list.get(p2).add(p1);
		}
		for(int i=1;i<=N;i++) {
			list.get(i).sort(null);
		}
		
		int size = list.get(V).size();
		visited = new boolean[N+1];
		dfs(V, size);
		visited = new boolean[N+1];
		bfs(V);
		System.out.println(sdfs);
		System.out.println(sbfs);
	}
    
    
	static void dfs(int target, int size) {
		if(visited[target]) return;
		
		visited[target] = true;
		sdfs.append(target).append(" ");
		
		for(int i=0;i<size;i++) {
			int x = list.get(target).get(i);
			if(!visited[x])
				dfs(x,list.get(x).size());
		}
	}
	
	static void bfs(int target) {
		visited[target] = true;		
		Queue<Integer> q = new LinkedList<>();
		q.offer(target);
		
		while(!q.isEmpty()) {
			int curr = q.poll();
			sbfs.append(curr).append(" ");
			
			for(int i=0;i<list.get(curr).size();i++) {
				int tmp = list.get(curr).get(i);
				if(visited[tmp]) continue;
				
				visited[tmp] = true;
				q.offer(tmp);
			}
		}
	
	}
}

 

풀이 (2)

인접 행렬을 이용한 구현

public class Main {	
	static int N, M, V;
	static int[][] matrix;
	static StringBuilder strDfs = new StringBuilder();
	static StringBuilder strBfs = new StringBuilder();
	
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine()," ");
		N = Integer.parseInt(st.nextToken());	// 정점 개수
		M = Integer.parseInt(st.nextToken());	// 간선 개수
		V = Integer.parseInt(st.nextToken());	// 시작 정점 번호
		matrix = new int[N+1][N+1];	// index가 1 based임 (정점번호: 1~N번)
		
		for(int i=0;i<M;i++) {
			st = new StringTokenizer(in.readLine()," ");
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());
			// 간선이 양방향으로 주어지기 때문에 둘다 표시해준다.
			matrix[from][to]= 1;
			matrix[to][from]= 1;
		}
		// dfs
		dfs(V, new boolean[N+1]);
		System.out.println(strDfs);
		
		// bfs
		bfs(V);
		System.out.println(strBfs);
	}
	static void dfs(int start, boolean[] visited) {
		visited[start] = true;
		strDfs.append(start).append(' ');
		
		for(int i=1;i<=N;i++) {
			if((matrix[start][i] == 1) &&!visited[i]) {
				dfs(i, visited);
			}
				
		}
	}
	static void bfs(int start) {
		boolean[] visited = new boolean[N+1];
		Queue<Integer> q = new LinkedList<>();
		
		q.add(start);
		visited[start] = true;
		
		while(!q.isEmpty()) {
			int node = q.poll();
			strBfs.append(node).append(' ');
			
			for(int i=1;i<=N;i++) {
				if(matrix[node][i]==1 && !visited[i]) {
					visited[i] = true;
					q.add(i);
				}
			}
			
		}
	}
}