[알고리즘 기초] 그래프, DFS/BFS/백트래킹, 길찾기문제 예시

👉 그래프

정점과 정점간의 관계를 표시하는 간선으로 구성된 자료

ex) 지하철 노선의 최단 경로 (지하철역 = 정점)

 

👉 그래프 구성요소

1) 정점 (Node, Vertex)

2) 간선 (Edge)

 

👉 그래프 관련 용어

1) 방향

• 방향 그래프
• 무방향 그래프 (=양방향 그래프)

2) 순환 (cycle)

• 순환 그래프
• 비순환 그래프

→ 어디에도 사이클이 하나라도 있으면 순환그래프

• 방향성 비순환 그래프 (DAG)→ 과거에서 미래로 계속 진행하기에 방향성
• → 미래에서 과거로 갈 수 없기에 비순환
• ex) 블록체인, 깃허브브랜치

3) 연결요소

• 1개 안에 있는 노드들은 서로 이동가능

 

👉 코드로 그래프 나타내는 방법

1) 인접행렬

• 검색 속도가 빠르다 O(1)

2) 인접리스트

• 차지하는 메모리가 적음
• 시간복잡도 O(n)
• 간선이 적어야 빛을 바란다

 

---

👉 DFS (Depth First Search)

• 깊이 우선 탐색
• 완전탐색 중 하나
• 스택이나 재귀를 사용
• 가장 아래까지 내려가는 방식

 

👉 BFS (Breadth First Search)

• 너비 우선 탐색
• 완전탐색 중 하나
• 큐를 사용
• 옆으로 넓게 퍼저나가는 방식

 

👉 백트래킹

• 가능성이 없는 경우에는 볼 필요가 없기에 다른 선택지를 보는 방법으로 경우의 수를 줄인다
• 완전탐색 중 하나
• DFS나 BFS를 사용

 

 

 

---

👉 길찾기 문제

✔️  DFS

재귀함수 이용

//동서남북 좌표
var dx = [1, 0, -1, 0]
var dy = [0, 1, 0, -1]

//방문체크 배열 (2차원배열 생성) //100*100사이즈
var checkArr = [[Bool]](repeating: Array(repeating: false, count: 100), count: 100)

//존재하는 길인지 확인
func isValid(y: Int, x: Int) -> Bool {
    return 0 <= y && y < 100 && 0 <= x && x < 100 ? true : false
}

var count = 0
//깊이 우선 탐색 시작
func dfs(y: Int, x: Int) {
    count += 1
    //동서남북으로 4번반복
    for k in 0..<4 {
        //다음 가야할 목적지
        let nextY = y + dy[k]
        let nextX = x + dx[k]
        
        //존재하는 길인지 확인 && 방문했는 지 확인 (방문했다면 true, 방문안했으면 false)
        if isValid(y: nextY, x: nextX) && !checkArr[nextY][nextX] {
            //방문했으니 true로 변경
            checkArr[nextY][nextX] = true
            //다음 갈 수 있는 길로 개척 (재귀함수호출)
            dfs(y: nextY, x: nextX)
        }
    }
}

//시작할 좌표
let startY = 0
let startX = 0
//시작하는 좌표는 현재 있는 위치로 방문체크
checkArr[startY][startX] = true
//탐색 시작
dfs(y: startY, x: startX)

print(count)

 

 

✔️  BFS

큐 이용

//동서남북 좌표
var dx = [1, 0, -1, 0]
var dy = [0, 1, 0, -1]

//존재하는 길인지 확인
func isValid(y: Int, x: Int) -> Bool {
    return 0 <= y && y < 100 && 0 <= x && x < 100 ? true : false
}

var count = 0
//너비 우선 탐색 시작
func bfs(startY: Int, startX: Int) {
    //방문체크 배열 (2차원배열 생성) //100*100사이즈
    var checkArr = [[Bool]](repeating: Array(repeating: false, count: 100), count: 100)
    //시작위치 방문 확인
    checkArr[startY][startX] = true
    
    let queue: Queue = Queue<[Int]>([])
    queue.push([startY, startX])
    
    //큐가 비어있지 않으면 계속 반복
    while !queue.isEmpty {
        count += 1

        //현재 위치
        let pop = queue.pop()
        let y = pop[0]
        let x = pop[1]
        
        //동서남북으로 4번반복
        for k in 0..<4 {
            //다음 가야할 목적지
            let nextY = y + dy[k]
            let nextX = x + dx[k]
            
            //존재하는 길인지 확인 && 방문했는 지 확인
            if isValid(y: nextY, x: nextX) && !checkArr[nextY][nextX] {
                checkArr[nextY][nextX] = true
                //다음 갈 위치를 큐에 추가 (다음 갈 위치가 있으면 계속 반복 진행)
                queue.push([nextY, nextX])
            }
        }
    }
}

//시작할 좌표
let startY = 0
let startX = 0
//탐색 시작
bfs(startY: startY, startX: startX)

print(count)

 

 

 

 

https://adela.love/posts/dfs-and-bfs

그래프 탐색을 위한 DFS와 BFS 알고리즘