백준_1260_DFS와 BFS

1, 

구분: DFS, BFS

언어: Python, Java

---

2, 코드

python

 

java

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;

public class BOJ_1260 {

	static int n; //정점의 개수
	static int[][] matrix; //정점간의 연결 관계를 나타낼 int형 2차원 배열
	static boolean[] visitD, visitB; //방문 여부를 파악하기 위한 boolean형 배열
	
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		
		n = scanner.nextInt();
		int m = scanner.nextInt(); //간선의 개수
		int start = scanner.nextInt(); //시작 점 
		
		matrix = new int[n+1][n+1];
		visitD = new boolean[n+1];
		visitB = new boolean[n+1];
		
		//정점들을 입력 받는다.
		for(int i = 0; i<m; i++) {
			int a = scanner.nextInt();
			int b = scanner.nextInt();
			matrix[a][b] = matrix[b][a] = 1;
		}
		
		DFS(start);
		System.out.println();
		BFS(start);
		
	}//main

	
	//재귀를 이용한 DFS
	public static void DFS(int node) {
		//들어온 것은 방문 처리 
		visitD[node] = true;
		System.out.print(node + " ");
		
		//해당 정점과 인접하면서 아직 방문하지 않은 노드를 찾아 재귀
		for(int i = 1; i<n+1; i++) {
			if(matrix[node][i]==1 && !visitD[i]) {
				DFS(i);
			}
		}
	}
	
	
	//큐를 이용한 BFS
	public static void BFS(int start) {
		Queue<Integer> queue = new LinkedList(); //queue를 정의
		queue.add(start);//시작점을 큐에 넣는다 
		visitB[start] = true;//큐에 넣은 것은 방문 처리 
		while(!queue.isEmpty()) {//큐가 안빌떄까지 
			int node = queue.poll();//큐에서 하나 뺴고
			System.out.print(node +" ");
			for(int i = 1; i<n+1; i++) {
				//해당 정점과 인접하면서 아직 방문하지 않은 노드를 찾아 큐에 넣고 방문 처리 
				if(matrix[node][i] == 1 && !visitB[i]) {
					queue.add(i);
					visitB[i] = true;
				}
			}
		}
		
	}
}

---

3, 

• 노드들의 연결 상태를 'graph'로 변환하는 방법을 몰라 구글링 하였다
• 번호가 작은 노드부터 탐색해야 하므로 'graph'안 각 리스트를 정렬했다
• 노드의 방문 상태를 저장하는 visited를 DFS와 BFS에서 동일하게 사용하여서 오류가 났다. 새로운 visited도 좋지만 다시 False로 초기화 한 후에 bfs를 호출하는 방법도 있을 것 같다.