[Swift][DFS] 백준 18290번 (NM과 K(1))

요구능력 : DFS

 

코드설명 : 

 

DFS문제이지만, 마냥 순열로 풀어버리면 DFS에 O(n^2)이 나와버려서 통과가 안된다.

그래서 처음에는 선택으로 가려고 x와 y둘다 이전에 방문했던 부분 다음 부분부터 방문하게했더니 ,

그렇게 하면 탐색하는 줄이 다음줄로 넘어가도 y좌표도 이전에 방문했던 부분의 다음부분부터 방문해버리는 문제가 생겨서

x만 중복을 최대한 줄이는 쪽으로 문제를 해결했다.

 

이거 외에 이 문제에서 핵심이라고 볼만한것은 바로 이 부분이다.

func check(_ x: Int, _ y: Int) -> Bool{
    for i in 0..<4{
        let nx = x + dx[i]
        let ny = y + dy[i]
        
        if nx < 0 || nx >= n || ny < 0 || ny >= m{ continue }
        if visited[nx][ny] { //현재 좌표와 인접한 곳이 이전에 방문한적 있었다면 현재좌표는 쓸 수 없다.
            return false
        }
    }
    return true
}

 

나만 그랬을 수도 있지만, 이전에 방문했던곳과 인접한곳도 방문해서는 안된다는걸 생각은 했는데 구현이 어려웠다.

이 부분을 고려하지 않았다면 틀리는 좋은 반례를 하나 질문에서 찾았다.

 

3 3 4
100 10 1
1000 2 1
10000 10 10000

답 : 20102

 

종합적으로 정리해보자면

dfs를 순열로 돌리지 않고 선택(?)으로 돌려서 시간을 줄였고,

현재 좌표와 인접한곳을 탐색해서 인접한곳을 방문한적이 없다면 현재좌표를 사용하는 방식으로 문제를 해결했다.

 

후기 : 전에 못풀었던거 오랜만에 풀어봤는데, 어디가 문제인지 눈에 보여서 풀기는 풀었다.

 

import Foundation
let nmk = readLine()!.split(separator: " ").map{Int(String($0))!}
let n = nmk[0]
let m = nmk[1]
let k = nmk[2]
var arr = [[Int]]()
let dx = [-1, 1, 0 ,0]
let dy = [0, 0, -1, 1]
var sum = 0
var result = -10001
for _ in 0..<n{
    arr.append(readLine()!.split(separator: " ").map{Int(String($0))!})
}

var location = [(Int, Int)]()
var visited = Array(repeating: Array(repeating: false, count: m), count: n)

func check(_ x: Int, _ y: Int) -> Bool{
    for i in 0..<4{
        let nx = x + dx[i]
        let ny = y + dy[i]
        
        if nx < 0 || nx >= n || ny < 0 || ny >= m{ continue }
        if visited[nx][ny] {
            return false
        }
    }
    return true
}
func dfs(_ depth: Int, _ startX: Int, _ startY: Int){
    if depth == k{
        result = max(result, sum)
        return
    }
    
    for i in startX..<n{
        for j in 0..<m{
            if !visited[i][j] && check(i, j){

                sum += arr[i][j]
                visited[i][j] = true
                location.append((i, j))
                dfs(depth + 1, i, j)
                sum -= arr[i][j]
                location.removeLast()
                visited[i][j] = false
                
                
            }
            
        }
    }
}
dfs(0, 0, 0)
print(result)