BFS 관련 문제입니다.

Question

미로 탈출인데 항상 마무리가 안되는거 같네요... for _, v := range dir { x1 := x + v[0] y1 := y + v[1] if x1 < 0 || y1 < 0 || x1 >= 9 || y1 >= 9 { continue } if m[y1][x1] != 0 { continue } queue.push11([x][y]) } }

데브폐인 · Answer

[chatGPT4]먼저, 주어진 코드는 BFS 알고리즘을 구현하기 위한 코드처럼 보이지만, 실제로는 DFS 알고리즘을 사용하고 있습니다. BFS 알고리즘을 사용하도록 코드를 수정하겠습니다. 또한, 주어진 미로의 크기가 8x8이므로, 마지막 인덱스는 7입니다. 이를 고려하여 코드를 수정하겠습니다.다음은 개선된 코드입니다:package main import ( "fmt" "os" ) type Position struct { x int y int } func bfs(m [][]int, startX, startY int) { queue := make([]Position, 0) queue = append(queue, Position{startX, startY}) m[startY][startX] = 2 dir := [][]int{{1, 0}, {0, 1}, {-1, 0}, {0, -1}} for len(queue) > 0 { curPos := queue[0] queue = queue[1:] if curPos.x == 7 && curPos.y == 7 { fmt.Println("yeah!") for _, v := range m { fmt.Println(v) } os.Exit(0) } for _, v := range dir { x1 := curPos.x + v[0] y1 := curPos.y + v[1] if x1 < 0 || y1 < 0 || x1 >= 8 || y1 >= 8 { continue } if m[y1][x1] != 0 { continue } queue = append(queue, Position{x1, y1}) m[y1][x1] = 2 } } } func main() { m := [][]int{ {0, 1, 0, 0, 0, 0, 0, 0}, {0, 1, 0, 1, 1, 1, 1, 0}, {0, 1, 0, 1, 0, 0, 0, 0}, {0, 1, 0, 1, 0, 1, 1, 0}, {0, 1, 0, 1, 0, 1, 0, 0}, {0, 1, 0, 1, 0, 1, 0, 0}, {0, 1, 0, 0, 0, 1, 0, 0}, {0, 1, 1, 1, 0, 0, 0, 0}, } bfs(m, 0, 0) }이 코드는 주어진 미로에서 BFS 알고리즘을 사용하여 0, 0에서 출발하여 7, 7까지 도달하는 가장 빠른 경로를 찾습니다. 도착지에 도달하면 "yeah!"을 출력하고 미로 상태를 출력한 후 종료합니다.

데브폐인 · Answer

dfs 를 사용한 경우 package main import ( "fmt" "os" ) type Position struct { x int y int } func dfs(m [][]int, x, y int) { if x == 7 && y == 7 { fmt.Println("yeah!") for _, v := range m { fmt.Println(v) } os.Exit(0) } dir := [][]int{{1, 0}, {0, 1}, {-1, 0}, {0, -1}} m[y][x] = 2 for _, v := range dir { x1 := x + v[0] y1 := y + v[1] if x1 < 0 || y1 < 0 || x1 >= 8 || y1 >= 8 { continue } if m[y1][x1] != 0 { continue } dfs(m, x1, y1) } m[y][x] = 0 } func main() { m := [][]int{ {0, 1, 0, 0, 0, 0, 0, 0}, {0, 1, 0, 1, 1, 1, 1, 0}, {0, 1, 0, 1, 0, 0, 0, 0}, {0, 1, 0, 1, 0, 1, 1, 0}, {0, 1, 0, 1, 0, 1, 0, 0}, {0, 1, 0, 1, 0, 1, 0, 0}, {0, 1, 0, 0, 0, 1, 0, 0}, {0, 1, 1, 1, 0, 0, 0, 0}, } dfs(m, 0, 0) }

BFS 관련 문제입니다.

2개의 답변

#go 목록