그래프 BFS DFS

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

1260번: DFS와 BFS

이 문제를 몇번이나 푸는지 모르겠지만

bfs/dfs문제들은 공백기가 생기면 초기화되는 매직 🥲

다시 풀려면 처음부터 공부하다보니 시간을 오래 잡아먹어서 이번기회에 제대로 잡고 가려고 포스팅을 한다.

 

이 포스팅에선 !!그래프와 관련된!! BFS/DFS만 다룬다.

//
//  1260.swift
//  BOJ
//
//  Created by leehwajin on 2023/01/09.
//

import Foundation
//1260 DFS와BFS
var nmv = readLine()!.split(separator: " ").map { Int(String($0))! }
let n = nmv[0]
let m = nmv[1]
let v = nmv[2]

var visited = Array(repeating: false, count: n+1)
var matrix = Array(repeating: Array(repeating: 0, count: n+1), count: n+1)

for _ in 0..<m { //그래프 2차원배열로 표현
    let nums = readLine()!.split(separator: " ").map{ Int(String($0))! }
    matrix[nums[0]][nums[1]] = 1
    matrix[nums[1]][nums[0]] = 1
}

func bfs(_ v: Int){
    var queue = [v]
    while !queue.isEmpty{
        let node = queue.removeFirst()
        print(node,terminator: " ")
        visited[node] = true
        for i in 1...n{
            if visited[i] == false && matrix[node][i] == 1{
                visited[i] = true
                queue.append(i)
            }
        }
    }
}

func dfs(_ start: Int) {
    visited[start] = true
    print(start, terminator: " ")
    for i in 1..<n+1 {
        if visited[i] == false && matrix[start][i] == 1 {
            dfs(i)
        }
    }
}

 

* 여기서 매트릭스 배열은 노드와의 관계를 저장하는 2차원 배열 (정사각형 배열)