[BOJ] 10164번 : 격자상의 경로(Go, Golang)

문제 링크 : 백준 10164번

[문제 접근]

로봇은 오른쪽 또는 아래쪽으로만 갈 수 있으므로 dp를 이용해서 풀면 될 것 같았다.

먼저 격자판을 의미하는 dp배열은 int형 num과 bool형 check를 가지는 구조체로 선언해준다.(bool형은 동그라미 표시칸을 지나온건지 아닌지를 나타낸다.)

1. 전체 격자판을 1과 false로 초기화 시켜준다.
2. k의 위치를 찾아서 그 위치를 기준으로 오른쪽, 아래쪽 전체의 check를 true로 변경해주어 동그라미 위치를 지나온 것으로 바꿔준다.
3. 조건
   • 구하려는 위치의 위쪽이나 왼쪽 둘다 false면 동그라미를 지나오지 않은 경로들이므로 각각의 num을 더해주고 check는 false로 저장한다.
   • 위쪽이나 왼쪽 중 하나가 true면 true인 곳만 동그라미를 지나온 경로이므로 true인 부분의 num만 가져온다.
   • 위쪽과 왼쪽 둘다 true면 둘다 동그라미를 지나온 경로들이므로 각각의 num을 더해주고 check는 true로 저장한다.
4. 3번 조건을 수행한 후 구하려는 위치의 check값이 true면 그 부분은 동그라미거나 동그라미가 지나온 경로이므로 무조건 true로 바꿔준다.(그림의 빨간색 부분을 처리하기 위한 방법)

최종적으로 dp[n][m].num을 출력해주면 된다.

[소스 코드]

package main

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

type node struct {
	num   int
	check bool
}

var n, m, k int
var dp [16][16]node

func main() {
	r := bufio.NewReader(os.Stdin)
	w := bufio.NewWriter(os.Stdout)
	defer w.Flush()
	fmt.Fscan(r, &n, &m, &k)

	for i := 1; i <= n; i++ {
		for j := 1; j <= m; j++ {
			dp[i][j] = node{
				num:   1,
				check: false,
			}
		}
	}
	if k != 0 {
		k--
		x := k / m
		y := k % m
		for i := x + 1; i <= n; i++ {
			for j := y + 1; j <= m; j++ {
				dp[i][j].check = true
			}
		}

	}

	for i := 2; i <= n; i++ {
		for j := 2; j <= m; j++ {
			num1 := dp[i-1][j].num
			num2 := dp[i][j-1].num
			temp1 := dp[i-1][j].check
			temp2 := dp[i][j-1].check
			nextnum := num1 + num2
			nextcheck := true
			if temp1 == false && temp2 == false {
				nextcheck = false
			} else if temp1 && temp2 == false {
				nextnum = num1
			} else if temp1 == false && temp2 {
				nextnum = num2
			}

			if dp[i][j].check {
				nextcheck = true
			}

			dp[i][j] = node{
				num:   nextnum,
				check: nextcheck,
			}
		}
	}

	fmt.Fprintln(w, dp[n][m].num)
}