[BOJ/Gold 5] 백준 17265 나의 인생에는 수학과 함께(Kotlin)

문제 링크

https://www.acmicpc.net/problem/17265

17265번: 나의 인생에는 수학과 함께

 

문제

세현이의 인생의 목표는 1분 1초 모든 순간 수학과 함께 살아가는 것이다. 그렇기 때문에 매일 수학을 생각하면서 살아가고 있다. 세현이는 밥을 먹을 때도 쌀알의 수를 계산하여 칼로리를 바로 계산하고 한걸음 한걸음 보폭을 계산하여 자신의 활동량을 확인하며 인생의 목표를 실행하며 살아가고 있다.  그런 세현이는 매일 학교를 가면서 지나가는 길에도 수학을 적용시키고 싶었다.

세현이네 집에서 학교까지 가는 길은 N x N 크기의 바둑판과 같다. 그리고 각 블록은 1 x 1 정사각형으로 구분 지을 수 있다. 세현이는 그 블록마다 숫자와 연산자가 존재한다고 생각해서 임의의 숫자와 연산자를 각 블록에 넣어 바둑판을 만들었다.

세현이는 학교에서 집으로 가는 경로에서 만나는 숫자와 연산자의 연산 결과의 최댓값과 최솟값을 구하려고 한다. 세현이는 항상 자신의 집 (1, 1)에서 학교 (N, N)까지 최단거리로 이동한다. 최단거리로 이동하기 위해서는 오른쪽과 아래쪽으로만 이동해야 한다.

 

 

위와 같이 N = 5 인 5 x 5 바둑판을 만들었다고 해보자.

그림 1의 경로를 통해 집(1, 1)에서 학교(N, N)까지 어떻게 연산이 되는지 확인해보자. 경로에서 만나는 연산자들의 우선순위는 고려하지 않는다.

1.  5 → × → 4 = 20
2.  20 → + → 5 = 25
3.  25 → ×→ 5 = 125
4.  125 → + → 2 = 127

그림 1은 최댓값을 가지는 경로이며 127이라는 최댓값을 얻을 수 있다.

그리고 위와 같이 연산하여 그림 2의 경로를 통해서 최솟값으로 3을 얻을 수 있다.

세현이는 이 길을 걸으면서 최댓값과 최솟값을 암산하다가 교통사고를 당해 현재 인하대학교 병원에 입원했다. 아픈 세현이를 위해 최댓값과 최솟값을 구해주자.

 

입력

첫 번째 줄에는 지도의 크기 N이 주어진다. (3 ≤ N ≤ 5, N은 홀수) 

그 다음 N 줄에는 N개의 숫자 또는 연산자가 빈칸을 사이에 두고 주어지며, 세현이네 집 (1, 1)과 학교 (N, N)는 반드시 숫자로 주어진다.

그리고 숫자 다음에는 연산자, 연산자 다음에는 숫자가 나오도록 주어진다. 주어지는 숫자는 0이상 5이하의 정수, 연산자는 (‘+’, ‘-’, ‘*’) 만 주어진다.

 

출력

연산 결과의 최댓값과 최솟값을 하나의 공백을 두고 출력한다. 연산자 우선순위는 고려하지 않는다.

 

예제 입력 1

5
5 + 5 - 3
* 3 - 1 -
4 + 5 + 2
- 2 * 3 -
1 * 5 + 2

예제 출력 1

127 3

 

 

알고리즘 분류

• 그래프 탐색

 

풀이

먼저 최댓값을 나타내는 변수는 -20억으로, 최솟값을 나타내는 변수는 20억으로 초기화한다.

그리고 배열의 크기와 배열을 입력받고 DFS를 수행한다.

(1, 1)부터 시작해서 오른쪽 또는 아래쪽으로만 이동하며 다음 칸이 연산자라면 해당 연산자를 저장하고, 다음 칸이 값이라면 현재까지 누적된 값과 다음 칸에 등장하는 값을 연산한다.

(N, N)에 도달했다면 지금까지 누적한 값과 최댓값, 최솟값 변수와 비교한다.

마지막으로 최댓값과 최솟값을 공백으로 구분하여 출력한다.

 

코드

import java.util.*
import kotlin.math.*

const val INF = 2e9
var resultMax: Int = -INF.toInt()
var resultMin: Int = INF.toInt()
var visited: Array<Array<Boolean>> = arrayOf()

fun dfs(y: Int, x: Int, value: Int, arr: Array<Array<String>>, n: Int, op: String) {
    if ((y == n - 1) && (x == n - 1)) {
        resultMax = max(resultMax, value)
        resultMin = min(resultMin, value)
        return
    }

    when (op) {
        "?" -> {
            if ((y < n - 1) && !visited[y + 1][x]) {
                visited[y + 1][x] = true
                dfs(y + 1, x, value, arr, n, arr[y + 1][x])
                visited[y + 1][x] = false
            }
            if ((x < n - 1) && !visited[y][x + 1]) {
                visited[y][x + 1] = true
                dfs(y, x + 1, value, arr, n, arr[y][x + 1])
                visited[y][x + 1] = false
            }
        }
        "+" -> {
            if ((y < n - 1) && !visited[y + 1][x]) {
                visited[y + 1][x] = true
                dfs(y + 1, x, value + arr[y + 1][x].toInt(), arr, n, "?")
                visited[y + 1][x] = false
            }
            if ((x < n - 1) && !visited[y][x + 1]){
                visited[y][x + 1] = true
                dfs(y, x + 1, value + arr[y][x + 1].toInt(), arr, n, "?")
                visited[y][x + 1] = false
            }
        }
        "-" -> {
            if ((y < n - 1) && !visited[y + 1][x]) {
                visited[y + 1][x] = true
                dfs(y + 1, x, value - arr[y + 1][x].toInt(), arr, n, "?")
                visited[y + 1][x] = false
            }
            if ((x < n - 1) && !visited[y][x + 1]) {
                visited[y][x + 1] = true
                dfs(y, x + 1, value - arr[y][x + 1].toInt(), arr, n, "?")
                visited[y][x + 1] = false
            }
        }
        "*" -> {
            if ((y < n - 1) && !visited[y + 1][x]) {
                visited[y + 1][x] = true
                dfs(y + 1, x, value * arr[y + 1][x].toInt(), arr, n, "?")
                visited[y + 1][x] = false
            }
            if ((x < n - 1) && !visited[y][x + 1]) {
                visited[y][x + 1] = true
                dfs(y, x + 1, value * arr[y][x + 1].toInt(), arr, n, "?")
                visited[y][x + 1] = false
            }
        }
    }
}

fun main() = with(Scanner(System.`in`)) {
    val n = nextLine().toInt()
    var arr: Array<Array<String>> = arrayOf()
    for (i in 0 until n) {
        val s = nextLine().split(' ')
        var temp = arrayOf<String>()
        var temp2 = arrayOf<Boolean>()
        for (j in s) {
            temp = temp.plus(j)
            temp2 = temp2.plus(false)
        }
        arr = arr.plus(temp)
        visited = visited.plus(temp2)
    }
    visited[0][0] = true
    dfs(0, 0, arr[0][0].toInt(), arr, n, "?")
    visited[0][0] = false

    println("$resultMax $resultMin")
}