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

 

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차원 배열로 작성되어 있으며 DFS(깊이 우선 탐색) 알고리즘과 STACK 자료구조를 활용하여 해결할 것이다.

 

---

해결 방안

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 readStack(){
    if stack.count != 0{
        cur.x = stack[stack.count-1].x
        cur.y = stack[stack.count-1].y
        stack.removeLast()
    }
}



var stack: [Location] = []

var cur = Location(0, 1)


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

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

이동할 때마다 현재 위치를 출력하였다.

---

구현을 마치고...

현재 위치에서의 경로를 탐색할 때 좌하우상 순서로 탐색을 하여 스택에 삽입하였다. 탐색 방향마다 "x"에 도착하는 시간을 단축할 수 있을 것이다.