7주차

계획

• 지난 주에 학습한 그래프 개념을 좀 더 학습한 뒤 예제풀이
• 기존 웹페이지 복습 및 발전

결과

• 지난 주 학습한 그래프 개념을 바탕으로 실제 예제를 풀이해보았다. 내가 직접 그래프를 만들고 이를 BFS, DFS로 탐색하는 알고리즘인데 먼저 그래프의 연결관계는 행렬로 표현한 후 재귀를 통해 탐색을 시도하였다. DFS는 내가 원하는대로 알고리즘이 구성되었지만, BFS를 이용하는 알고리즘은 완성하지 못했다. 흔히 큐를 이용하여 BFS를 구현한다고 하는데 나는 앞서 한 DFS와 마찬가지로 재귀를 사용하고 싶었기에 문제가 생긴 듯 하다. 추후 코드를 보완해보고 만약 원하는 결과가 나오지 않는다면 다른 자료구조로 풀이해봐야 겠다. 사용한 코드는 다음과 같다.

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int inputNum1, inputNum2;
		int[][] arr;
		int[] arr2, arr3;
		int i = scan.nextInt();
		int j = scan.nextInt();
		int k = scan.nextInt();
		arr = new int[i][i];
		arr2 = new int[i];	
		arr3 = new int[i];

		for (int a = 0; a < j; a++) {
			inputNum1 = scan.nextInt();
			inputNum2 = scan.nextInt();
			arr[inputNum2 - 1][inputNum1 - 1] = arr[inputNum1 - 1][inputNum2 - 1] = 1;
		}
	
			Ds(arr, arr2, k, i);
		System.out.println();
		Bs(arr, arr3, k, i);
	}

	public static void Ds(int[][] arr, int[] arr2, int k, int j) {
		System.out.print(k + " ");
		arr2[k - 1] = 1;
		for (int i = 0; i < j; i++) {
			if (arr[k - 1][i] == 1 && arr2[i] != 1) {
			    arr2[i]=1;
				Ds(arr, arr2, i + 1, j);
			}
		}
	}