백준 욕심쟁이판다 (Python/Go)

문제 링크: www.acmicpc.net/problem/1937

1937번: 욕심쟁이 판다

단순히 bfs로 완전탐색하면 시간초과가 나기 때문에 dfs+dp로 풀어야하는 난이도 있는 문제입니다.

핵심은 2차원 dp를 만들어서 dp에 0이 아닌 값이 있다면 탐색을 그만하고 그 값을 사용하면 됩니다.

예를 들어 (2, 2)에서 출발하였고 위로 1칸 갔다고 가정해본다면 (1, 2) 좌표입니다. dp[1][2] = 3 이런식으로 값이 저장되어 있다면 더 이상 탐색을 그만하고 3 + 1 값을 얻으면 됩니다. (+1은 출발한 칸에서도 판다가 하루는 살 수 있기 때문입니다.)

아래는 파이썬 코드입니다. 파이썬으로 백준 제출시 주의할 점이 하나있습니다. 보통 파이썬으로 제출하면 시간초과 문제 때문에 pypy3로 제출을 하실텐데 이 문제 같은 경우 pypy3로 제출하면 메모리초과가 나오고 python3로 제출하면 통과합니다. 이유는 잘 모르겠습니다.

 

아래는 Golang 코드입니다.

package main
 
import (
    "bufio"
    "fmt"
    "os"
    "strconv"
    "strings"
)
 
var n int
var board [][]int
var dp [][]int
var dx = []int {0, 0, -1, 1}
var dy = []int {-1, 1, 0, 0}
 
 
func max(x, y int) int {
    if x < y {
        return y
    }
    return x
}
 
func dfs(x, y int) int {
    if dp[x][y] > 0 {
        return dp[x][y]
    }
 
    dp[x][y] = 1  // 첫칸은 1
 
    for i:=0; i<4; i++ {
        nx, ny := x+dx[i], y+dy[i]
        if 0<=nx && nx<n && 0<=ny && ny<n {
            if board[nx][ny] > board[x][y] {
                dp[x][y] = max(dp[x][y], dfs(nx, ny)+1)
            }
        }
    }
 
    return dp[x][y]
 
}
 
func changeToInt(s string) []int {  // input으로 받은 숫자들 type 변경(string -> int)
    var numList []int
    for _, text := range strings.Fields(s) {
        num, _ := strconv.Atoi(text)
        numList = append(numList, num)
    }
    return numList
}
 
func main() {
 
    fmt.Scanln(&n)
 
    board = make([][]int, n)  // 대나무
    dp = make([][]int, n)
    scanner := bufio.NewScanner(os.Stdin)
    for i:=0; i<n; i++ {       // input 값으로 대나무 채우기
        scanner.Scan()
        nums := scanner.Text()
        line := changeToInt(nums)
        board[i] = line
        dp[i] = make([]int, n)  // dp는 0으로 초기
    }
 
    answer := 0
    for i:=0; i<n; i++ {
        for j:=0; j<n; j++ {
            answer = max(answer, dfs(i, j))
        }
    }
 
    fmt.Println(answer)
}
 
 

파이썬은 1052ms, Go는 88ms가 나오며 메모리도 Go가 훨씬 적게 나옵니다.