1260번 'DFS와 BFS'

import java.io.*;

import java.util.*;

class Main {

static ArrayList<Integer>[] arrayList;

static boolean[] isChecked;

public static void main(String[] args) throws IOException {

BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

String[] firstLine = in.readLine().split(" ");

final int numberOfVertex = Integer.parseInt(firstLine[0]);

final int numberOfEdge = Integer.parseInt(firstLine[1]);

final int startVertex = Integer.parseInt(firstLine[2]);

arrayList = new ArrayList[numberOfVertex + 1];

for(int i=1; i<=numberOfVertex; ++i) {

arrayList[i] = new ArrayList<>();

}

//간선 입력받고 어레이리스트에 저장

for(int i=0; i<numberOfEdge; ++i) {

String[] input = in.readLine().split(" ");

int u = Integer.parseInt(input[0]);

int v = Integer.parseInt(input[1]);

arrayList[u].add(v);

arrayList[v].add(u);

}

for(int i=1; i<=numberOfVertex; ++i) {

Collections.sort(arrayList[i]);

}

isChecked = new boolean[numberOfVertex + 1];

dfs(startVertex);

System.out.println();

isChecked = new boolean[numberOfVertex + 1];

bfs(startVertex);

System.out.println();

}

static void bfs(int start) {

//너비우선탐색: 큐 활용

Queue<Integer> queue = new LinkedList<>();

queue.add(start);

isChecked[start] = true;

while(!queue.isEmpty()) {

int vertex = queue.remove();

System.out.print(vertex + " ");

for(int edge: arrayList[vertex]) {

if(isChecked[edge] == false) {

isChecked[edge] = true;

queue.add(edge);

}

}

}

}

static void dfs(int start) {

//깊이우선탐색: 스택, 재귀호출 활용

if(isChecked[start] == true) {

return;

}

isChecked[start] = true;

System.out.print(start + " ");

for(int edge: arrayList[start]) {

if(isChecked[edge] == false) {

dfs(edge);

}

}

}

}

DFS (깊이 우선 탐색) : 최대한 깊숙히, 많이 탐색

- 스택, 재귀호출을 이용

- 해당 정점이 탐색되었는지 체크할 Bool 타입 배열이 필요하다.

- 재귀호출을 사용할 때, 해당 정점이 탐색되었으면 return 해주어야 한다.

- 정점은 탐색되고, 해당 정점으로부터의 간선을 저장한 ArrayList를 순회한다.

- 탐색되지 않은 정점을 찾아 그 정점에서 함수를 재귀호출한다.

BFS (너비 우선 탐색) : 최대한 넒게 탐색, 최단거리

- 큐를 이용

- 해당 정점이 탐색되었는지 체크할 Bool 타입 배열이 필요하다.

- 해당 정점은 탐색되고, 큐에 넣는다.

- 큐의 요소를 빼고, 그 요소로부터의 간선을 저장한 ArrayList를 순회한다.

- 탐색되지 않은 정점을 탐색하였다고 기록하고, 그 정점을 큐에 저장한다.

- 위의 두 문장을 큐가 빌 때까지 진행한다.

기본적으로 위의 사항들을 따라 차근차근 구현하자.

let firstLine = readLine()!.split(separator: " ").map { Int($0)! }

let numberOfVertex = firstLine[0]

let numberOfEdge = firstLine[1]

let startVertex = firstLine[2]

var array = [[Int]].init(repeating: [], count: numberOfVertex + 1)

var isChecked = [Bool].init(repeating: false, count: numberOfVertex + 1)

func bfs(start: Int) {

    var queue = [Int]()

    isChecked[start] = true

    queue.append(start)

    while !queue.isEmpty {

        let element = queue.removeFirst()

        print(element, terminator: " ")

        for vertex in array[element] {

            if !isChecked[vertex] {

                isChecked[vertex] = true

                queue.append(vertex)

            }

        }

    }

}

func dfs(start: Int) {

    if isChecked[start] {

        return

    }

    isChecked[start] = true

    print(start, terminator: " ")

    for vertex in array[start] {

        if !isChecked[vertex] {

            dfs(start: vertex)

        }

    }

}

for _ in 1...numberOfEdge {

    let input = readLine()!.split(separator: " ").map { Int($0)! }

    let u = input[0]

    let v = input[1]

    array[u].append(v)

    array[v].append(u)

}

for i in 1...numberOfVertex {

    array[i].sort()

}

dfs(start: startVertex)

print()

isChecked = [Bool].init(repeating: false, count: numberOfVertex + 1)

bfs(start: startVertex)

print()