[백준] 1260 DFS와 BFS (Java)

한비·2023년 2월 23일
0

baekjoon

목록 보기
6/7

백준 1260 DFS와 BFS

문제


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

입력


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

출력


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

예제 입력 1


4 5 1
1 2
1 3
1 4
2 4
3 4

예제 출력 1


1 2 4 3
1 2 3 4

예제 입력 2


5 5 3
5 4
5 2
1 2
3 4
3 1

예제 출력 2


3 1 2 5 4
3 1 4 2 5

예제 입력 3


1000 1 1000
999 1000

예제 출력 3


1000 999
1000 999

풀이


  • 입력으로 주어진 간선의 정보를 저장히기 위해 인접행렬을 사용한다.
  • 정점의 값을 그대로 배열의 index로 사용하기 위해 범위보다 1 큰 크기의 2차원 배열을 선언하고, 입력 받은 간선 정보에 해당하는 배열 값을 1로 한다.(가중치가 없는 그래프이기 때문에 인접해 있는 지 아닌 지만 판단하기 위해 1 사용)
  • DFS 수행
  • BFS 수행

코드



import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main{
	static int n, m, V;
	static int[][] nums;
	static boolean[] visited;
	static StringBuilder sb = null;
	static Queue<Integer> q;
	public static void main(String[] args) throws IOException, NumberFormatException{
		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());
		
		// 정점 값을 그대로 배열의 인덱스로 사용하기 위해 
		// N의 범위보다 1 더 큰 크기로 선언
		nums = new int[1001][1001];
		
		for(int i=0; i<m; i++) {
			st = new StringTokenizer(br.readLine());
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());
			
			// 양방향 간선이므로 양쪽 다 1로 만들기
			// 가중치 없는 그래프이므로 1
			// 1이면 인접, 0이면 인접 ㄴㄴ
			nums[from][to] = nums[to][from] = 1;
		}
		
		visited = new boolean[1001];
		sb = new StringBuilder();
		dfs(V);
		System.out.println(sb);
		
		visited = new boolean[1001];
		sb = new StringBuilder();
		bfs(V);
		System.out.println(sb);

	}
	static void dfs(int index) {
		// 시작 정점
		visited[index] = true;
		sb.append(index + " ");

		// 끝까지 탐색 다 하면 return
		if(index == n+1) return;
		
		
		for(int i=1; i<n+1; i++) {
			// 인접해있고, 탐색하지 않은 경우
			if(nums[index][i] == 1&&!visited[i])
				dfs(i);
		}
	}
	static void bfs(int index) {
		q = new ArrayDeque<>();
		// 시작 정점
		q.add(index);
		visited[index] = true;
		sb.append(index + " ");
		
		while(!q.isEmpty()) {
			int now = q.poll();
			for(int i=1; i<n+1; i++) {
				// 인접해있고, 탐색하지 않은 경우
				if(nums[now][i] == 1&&!visited[i]) {
					q.add(i);
					visited[i]= true;
					sb.append(i + " ");
				}
			}
		}
	}
}
profile
아기 개발자 한비의 두비두밥

0개의 댓글