[백준] (Swift) 18290번 - NM과 K(1) (feat. 브루트포스, DFS, 백트래킹)

🟠 문제 

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

18290번: NM과 K (1)

🟠 내가 푼 풀이

처음 보고 완전 참색에 DFS를 사용하면 되겠구나! 까지는 생각이 났다. (이전에 반복해서 푼 N과 M문제 덕분..)... 근데,,, 이제 그 후에 어떻게 해야할것인지 고민이 필요했다. 

문제를 요약하면 다음과 같다.

1. 2차원 배열을 입력받는다 (세로 N 가로 M)
2. 배열 내부에서 K개의 숫자를 뽑아서 합을구할 건데, 그 합이 최대가 되어야 한다. 
3. K개를 뽑을때 인접한 숫자는 고르면 안된다. 

일단,,, for문 두개를 돌려서 2차원 배열을 돌아가면서 하나씩 전부 탐색해주어야한다고 판단했고, 그 합을 구하는 과정에서 '상하좌우'로 돌려서 그 주변에 visited된 이력이 없다면! 더해주고, 만약 있다면 해당 위치를 그냥 넘어가는 방식으로 진행해야겠다고 생각했다.
이렇게 판단을 해보고, 재귀를 이용해야 하기 때문에 재귀가 어떻게 돌아가는지 그림으로 그려서 생각해봤다.

예제 4번으로 한 바퀴만 돌려본 재귀

이렇게 돌아가게 되겠지? 그리고 마지막에 count 즉, depth가 k (여기선3)가 되는 순간 dfs에서 return을 해주면 된다. 그래서 dfs가 시작할때 depth를 검사해주면 되겠구나! 싶었다. (N과 M 시리즈의 코드와 흘러가는게 거의 동일하다.

 

🟠 정답코드

return 하고, 해당 진행했던 내용을 다시 리셋하고 탐색을 돌아야하기 때문에 visited에서 false를 해주었다. 

중간에 있는 tempY는 아래와 같이 설명할 수 있다.

만약 이전 행과 현재 바라볼 행이 같다면 이전 열에 이어서 탐색하고, 만약 이전 행과 현재 바라볼 행이 같지 않다면 0부터 시작하겠다는 코드이다. 즉, (1,2) -> (1,5) -> (3,4) 에서 (1,5) 가 시작점이 될 때 (1,2) 와는 행이 같으므로 (1,2)를 제외하고 탐색하게 된다.
(참고: https://minoflower.tistory.com/50)

import Foundation

let nmk = readLine()!.split(separator: " ").map{ Int($0)! }
let n = nmk[0]
let m = nmk[1]
let k = nmk[2]
var arr = [[Int]]()
for _ in 0..<n {
    arr.append(readLine()!.split(separator: " ").map{ Int($0)! })
}
var visited = Array(repeating: Array(repeating: false, count: m), count: n)
var answer = -999999

let dx = [-1, 1, 0, 0] // 상하좌우
let dy = [0, 0, -1, 1]

private func dfs(px: Int, py: Int, depth: Int, maxNum: Int) {
    if depth == k {
        answer = max(maxNum, answer)
        return
    }

    for x in px..<n {
        let tempY = x == px ? py : 0
        for y in tempY..<m {
            if visited[x][y] {
                continue
            }

            var flag = true
            // 해당 xy 상하좌우에 하나라도 방문한 이력이 있으면 false
            for i in 0..<4 {
                let nx = x + dx[i]
                let ny = y + dy[i]

                if nx >= 0, ny >= 0, nx < n, ny < m {
                    if visited[nx][ny] {
                        flag = false
                    }
                }
            }

            // flag가 아직 true면 상하좌우 아무데도 아직 visited 한적이 없다는 뜻
            // 해당 위치 (xy)에 방문해서 answer에 더해주고 dfs 돌려주자
            if flag {
                visited[x][y] = true
                dfs(px: x, py: y, depth: depth + 1, maxNum: maxNum + arr[x][y])
                visited[x][y] = false
            }
        }
    }
}

dfs(px: 0, py: 0, depth: 0, maxNum: 0)
print(answer)