[백준 1260] DFS와 BFS (자바)

백준 1260번 DFS와 BFS  (자바)소수 찾

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

1260번: DFS와 BFS

 

 

문제

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

 

 

입력

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

 

 

입출력 예

 

입출력 1

 

입출력 2

 

입출력 3

 

한 줄 요약

DFS와 BFS를 이용해 정렬된 행렬을 출력해야 한다.

 

 

* DFS와 BFS를 모르는 분은 https://hidelookit.tistory.com/31?category=960062를 참고해주시기 바란다.

 

 

내 코드

1. main에서 행렬을 만들어야 한다.

    - 정점, 간선, 시작 정점 번호를 입력받고 행렬을 저장할 ['정점+1']['정점+1'] 크기의 이차원 배열 a를 생성한다.

    - 방문 여부를 판별할 boolean 배열 c를 생성한다.

    - 간선 크기만큼 반복문을 돌려 인접행렬을 저장한다. 인접원소는 1을 넣어준다.

    - dfs(a, c, v) 메소드를 실행한다.

 

2. dfs(재귀)

    - 반복문을 돌리기 위한 크기(a.length - 1)를 정수형 변수 n에 대입한다.

    - 방문의 표시로 첫 시작 정점의 방문여부를 'c[v] = true'로 변경한다.

    - System.out.print(v + " "); 로 정렬된 배열을 보여준다.

    - i(1~n)까지 반복문을 돌려 인접 원소인데 방문하지 않은(a[v][i] == 1 && !c[i]) 경우 dfs(a, c, i)를 실행한다.

    - 결과적으로 조건 충족 시 계속 dfs() 메서드가 출력되어 i가 출력되게 된다.

 

3. bfs

    - 원소를 담을 Queue를 생성한다.

    - 반복문을 돌리기 위한 크기(a.length - 1)를 정수형 변수 n에 대입한다.

    - q에 v를 넣는다.

    - 방문의 표시로 첫 시작 정점의 방문 여부를 'c[v] = true'로 변경한다.

    - q가 비어있지 않을 경우 while문을 계속 실행시킨다.

    - q의 첫 번째 원소를 꺼내고 삭제시킨다.

    - System.out.print(v + " "); 로 정렬된 배열을 보여준다.

    - i(1~n)까지 반복문을 돌려 인접 원소인데 방문하지 않은(a[v][i] == 1 && !c[i]) 경우 q에 i를 넣고, 방문처리(c[i] = true)를 한다.

    - bfs는 재귀 구조가 아니기 때문에 메서드를 계속 부르지 않는다.

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

public class DFS2 {
	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt(); // 정점
		int M = sc.nextInt(); // 간선
		int V = sc.nextInt(); // 시작 정점 번호

		int[][] a = new int[N+1][N+1];
		boolean[] c = new boolean[N+1];

		// 인접행렬 만들기
		for (int i = 0; i < M; i++) {
			int a1 = sc.nextInt();
			int a2 = sc.nextInt();

			a[a1][a2] = 1;
			a[a2][a1] = 1;
		}

		dfs(a, c, V);
		System.out.println();

		Arrays.fill(c, false);
		bfs(a, c, V);

	}

	//bfs
	//큐 사용
	private static void bfs(int[][] a, boolean[] c, int v) {
		Queue<Integer> q = new LinkedList<Integer>();
		int n = a.length - 1;
		q.add(v);
		c[v] = true;
		
		while (!q.isEmpty()) {
			v = q.poll();
			System.out.print(v + " ");
			
			for (int i=1; i<=n; i++) {
				if (a[v][i] == 1 && !c[i]) {
					q.add(i);
					c[i] = true;
				}
			}
			
		}
	}

	//재귀
	private static void dfs(int[][] a, boolean[] c, int v) {
		int n = a.length - 1;
		c[v] = true;
		System.out.print(v + " ");
		
		for (int i=1; i<=n; i++) {
			if (a[v][i] == 1 && !c[i]) {
				dfs(a, c, i);
			}
		}
	}

	// 스택
//	private static void dfs(int[][] a, boolean[] c, int v) {
//		Stack<Integer> stack = new Stack<Integer>();
//		int n = a.length - 1;
//		stack.push(v);
//
//		c[v] = true;
//		System.out.print(v + " ");
//
//		while (!stack.isEmpty()) {
//			int vv = stack.peek();
//			boolean flag = false;
//
//			for (int i = 1; i <= n; i++) {
//				if (a[vv][i] == 1 && !c[i]) {
//					stack.push(i);
//					System.out.print(i + " ");
//
//					c[i] = true;
//					flag = true;
//					break;
//				}
//			}
//
//			if (!flag) {
//				stack.pop();
//			}
//		}
//
//	}
}

 

DFS와 BFS의 원리를 이해하는 것이 첫 번째!