[Swift] Data Structure/maze search/BFS/queue/미로 탐색/너비우선탐색/큐

 

dbguswls030/Argorithm

---

문제 설명

var map = [
["1","1","1","1","1","1"],
["e","0","1","0","0","1"],
["1","0","0","0","1","1"],
["1","0","1","0","1","1"],
["1","0","1","0","0","x"],
["1","1","1","1","1","1"]]

현재 위치가 "e"일 때 "x"까지 도달하는 프로그램을 작성해야 한다.

"1"은 이동할 수 없는 길이며, "0"인 길로만 이동할 수 있다.

 

맵은 2차원 배열로 작성되어 있으며 BFS(너비 우선 탐색) 알고리즘과 Queue 자료구조를 활용하여 해결할 것이다.

---

해결 방안

 

1. 현재 위치 저장하기
2. 현재 위치를 "0"이 아닌 다른 값으로 변경하여 지나온 길 표시하기 -> 필자는 "e"로 변경함
3. 현재 위치에서 이동 가능한 경로 큐에 삽입하기
4. 큐에 있는 경로로 이동하기
5. 2~4 과정을 현재 위치가 "x"일 때까지 반복하기

 

---

import Foundation

var map = [
["1","1","1","1","1","1"],
["e","0","1","0","0","1"],
["1","0","0","0","1","1"],
["1","0","1","0","1","1"],
["1","0","1","0","0","x"],
["1","1","1","1","1","1"]]

struct Location {
    var x: Int
    var y: Int
    
    init(_ x : Int, _ y : Int) {
        self.x = x
        self.y = y
    }
}



func searchPath(){
    
    print(cur.y, cur.x)

    map[cur.y][cur.x] = "e"

    //search left
    if cur.x-1>=0{
        if map[cur.y][cur.x-1] == "0" || map[cur.y][cur.x-1] == "x"{
            stack.append(Location(cur.x-1, cur.y))
        }
    }

    //search down
    if cur.y-1>=0{
        if map[cur.y-1][cur.x] == "0" || map[cur.y-1][cur.x] == "x"{
            stack.append(Location(cur.x, cur.y-1))
        }
    }

    //search right
    if cur.x+1 <= map.count-1{
        if map[cur.y][cur.x+1] == "0" || map[cur.y][cur.x+1] == "x"{
            stack.append(Location(cur.x+1, cur.y))
        }
    }

    //search up
    if cur.y+1 <= map.count-1{
        if map[cur.y+1][cur.x] == "0" || map[cur.y+1][cur.x] == "x"{
            stack.append(Location(cur.x, cur.y+1))
        }
    }
}

func readQueue(){
    if stack.count != 0{
        cur.x = stack[0].x
        cur.y = stack[0].y
        stack.removeFirst()
    }
}


var stack: [Location] = []

var cur = Location(0, 1)


while map[cur.y][cur.x] != "x"{    
    searchPath()
    readQueue()    
}

print(map[cur.y][cur.x])

 

 

DFS로 구현한 것보다 더 오래 걸린다.............

[Swift] Data Structure/maze search/DFS/stack/미로 탐색/깊이우선탐색/스택

---

구현을 마치고...

큐로 구현한 것 또한 현재 위치에서 경로 탐색 순서를 어떻게 정하느냐에 따라 프로그램 시간이 좌우될 것이다.