[BOJ] 1600번 : 말이 되고픈 원숭이(Go, Golang)

문제 링크 : 백준 1600번

[문제 접근]

BFS로 접근해서 풀었다.
능력을 쓴 경우, 안쓴 경우를 각각 한 queue에서 돌리면 된다.

단, k를 몇 번이나 썼냐에 따라서 visit배열을 다르게 설정해줘야한다. 그래서 3차원 배열을 사용했다.

[소스 코드]

package main

import (
	"bufio"
	"fmt"
	"os"
)

var (
	read         = bufio.NewReader(os.Stdin)
	write        = bufio.NewWriter(os.Stdout)
	k, w, h, ans int
	arr          [201][201]int
	visit        [201][201][31]bool
	dx           = [4]int{-1, 1, 0, 0}
	dy           = [4]int{0, 0, 1, -1}
	hx           = [8]int{1, 2, 2, 1, -1, -2, -2, -1}
	hy           = [8]int{2, 1, -1, -2, -2, -1, 1, 2}
)

type pair struct {
	x, y, cnt, result int
}

func BFS() {
	// q를 x,y,cnt 구조체로 선언
	q := []pair{pair{x: 0, y: 0, cnt: 0, result: 0}}
	visit[0][0][0] = true

	for len(q) > 0 {
		x := q[0].x
		y := q[0].y
		num := q[0].cnt
		re := q[0].result
		q = q[1:]

		if x == h-1 && y == w-1 {
			ans = re
			break
		}

		if num < k {
			for i := 0; i < 8; i++ {
				nx := x + hx[i]
				ny := y + hy[i]

				if nx < 0 || ny < 0 || nx >= h || ny >= w || arr[nx][ny] == 1 || visit[nx][ny][num+1] {
					continue
				}

				q = append(q, pair{x: nx, y: ny, cnt: num + 1, result: re + 1})
				visit[nx][ny][num+1] = true
			}
		}
		for i := 0; i < 4; i++ {
			nx := x + dx[i]
			ny := y + dy[i]

			if nx < 0 || ny < 0 || nx >= h || ny >= w || arr[nx][ny] == 1 || visit[nx][ny][num] {
				continue
			}

			q = append(q, pair{x: nx, y: ny, cnt: num, result: re + 1})
			visit[nx][ny][num] = true
		}
	}
}

func main() {
	defer write.Flush()
	fmt.Fscan(read, &k, &w, &h)
	for i := 0; i < h; i++ {
		for j := 0; j < w; j++ {
			fmt.Fscan(read, &arr[i][j])
		}
	}
	ans = -1
	BFS()
	fmt.Fprintln(write, ans)
}