golang 미로 코드 구현

골랑 미로 코드 구현

미로 게임은 컴퓨터 프로그래밍 분야의 매우 고전적인 알고리즘 문제이며 프로그래밍 기술과 알고리즘적 사고를 연습하기에 좋은 사례이기도 합니다. 이 글에서는 미로 게임 코드를 GO 언어로 구현하는 방법을 소개합니다.

1. 미로 지도 초기화

먼저 미로 지도를 초기화하고 미로를 표현하는 행렬을 만들어야 합니다. 구현 과정에서 각 미로 셀을 노드로 간주하고 이를 2차원 배열로 표현할 수 있습니다. 미로 셀의 값은 현재 위치를 걸을 수 있는지, 걸을 수 없는지를 나타낼 수 있다.

미로의 벽을 0으로, 움직일 수 있는 공간을 1로 표현할 수 있습니다. 미로 지도를 초기화할 때 모든 초기 그리드를 0으로 설정합니다. 미로 가장자리의 그리드를 0으로 설정하여 걸을 수 없음을 나타냅니다. 미로의 가장자리 설정을 통해 솔루션을 찾을 때 가장자리 노드를 보다 편리하게 처리할 수 있습니다.

코드 구현은 다음과 같습니다.

type point struct{x, y int}

func (p point)add(other point)point {
    return point{p.x + other.x, p.y + other.y}
}

var directions = [4]point{
    {-1, 0}, {0, -1}, {1, 0}, {0, 1},
}

func (g Grid)at(p point) gridValue {
    if p.x < 0 || p.x >= g.width {
        return wall
    }
    if p.y < 0 || p.y >= g.height {
        return wall
    }
    return g.cells[p.y][p.x]
}

func (g Grid)set(p point, v gridValue) {
    g.cells[p.y][p.x] = v
}

type Grid struct {
    width, height int
    cells         [][]gridValue
}

type gridValue byte

const (
    empty gridValue = iota
    wall
    start
    end
    path
)

func newGrid(width, height int) Grid {
    cells := make([][]gridValue, height)
    for i := range cells {
        cells[i] = make([]gridValue, width)
        for j := range cells[i] {
            cells[i][j] = empty
        }
    }
    return Grid{width: width, height: height, cells: cells}
}

2. 미로에서 빠져나오기

깊이 우선 탐색(DFS) 알고리즘을 사용하여 미로의 시작점부터 끝까지 이동하여 모든 경로를 표시할 수 있습니다. DFS 알고리즘은 스택 방식을 사용하여 특정 끝점에 도달하거나 계속할 수 없는 위치에 도달할 때까지 한 방향으로 계속 이동합니다. 진행할 수 없는 위치에 도달하면 이전 위치로 돌아가서 끝점을 찾거나 모든 경로를 통과할 때까지 프로세스를 반복합니다.

다음은 DFS 알고리즘을 사용하여 구현한 코드입니다.

func (g Grid)solveDFS() {
    start := g.findStart()
    g.dfsRecursive(start)
}

func (g Grid)findStart() point {
    for y, row := range g.cells {
        for x, value := range row {
            if value == start {
                return point{x, y}
        }
    }
  }
  panic("start point not found")
}

func (g Grid)dfsRecursive(current point) {
    if !g.inBounds(current) || g.at(current) == wall {
        return
    }
    if g.at(current) == end {
        return
    }
    g.set(current, path)
    for _, direction := range directions {
        g.dfsRecursive(current.add(direction))
    }
}

3. 미로에서 최단 경로 찾기

DFS 알고리즘은 끝까지 모든 경로를 찾을 수 있지만 최단 경로를 찾을 수는 없습니다. 최단 경로를 찾기 위해서는 BFS(Breadth First Search) 알고리즘을 사용해야 합니다. BFS 알고리즘은 최단 경로를 찾는 알고리즘입니다.

BFS 알고리즘은 시작점에서 시작하여 끝점에 도달할 때까지 현재 대기열의 모든 인접 노드를 확장하는 대기열 방법을 사용합니다. 끝점을 찾으면 반대 방향으로 되돌아가서 최단 경로를 표시해야 합니다.

다음은 BFS 알고리즘을 사용하여 구현한 코드입니다.

type node struct {
    point
    distance int
}

func (g Grid)solveBFS() {
    start := g.findStart()
    queue := []node{{point: start}}
    seen := map[point]bool{start: true}
    for len(queue) > 0 {
        current := queue[0]
        queue = queue[1:]
        if g.at(current.point) == end {
            g.markShortestPath(current)
            return
        }
        for _, direction := range directions {
            next := current.add(direction)
            if !g.inBounds(next) || seen[next] || g.at(next) == wall {
                continue
            }
            seen[next] = true
            queue = append(queue, node{point: next, distance: current.distance + 1})
        }
    }
}

func (g Grid)markShortestPath(current node) {
    for ; g.at(current.point) != start; current.distance-- {
        g.set(current.point, path)
        for _, direction := range directions {
            next := current.add(direction)
            if g.at(next) == path && current.distance - 1 == g.at(next).distance {
                current.point = next
                break
            }
        }
    }
}

위 코드에서는 노드 좌표와 노드까지의 거리를 포함하는 노드 구조를 정의합니다. BFS 알고리즘에서는 현재 검색해야 하는 노드를 큐에 저장하고, 반복 검색을 피하기 위해 방문한 노드를 맵에 기록합니다. 검색 과정에서 끝점을 찾을 때까지 각 노드에서 시작점까지의 거리를 기록합니다. 그런 다음 최단 경로를 역추적하고 순회하고 해당 경로에 경로라는 레이블을 붙입니다.

위 내용은 golang 미로 코드 구현의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!