[Swift][BruteForce] 백준 16197번 (두 동전)

요구능력 : 백트래킹

 

코드설명 : 

 

문제를 보면 동전이 한 칸씩 왔다갔다 해야된다.

그래서 백트래킹을 생각했고 백트래킹을 하기위해서는 동전의 위치좌표가 필요했다.

 

이 문제에서의 핵심

1. 두 동전의 위치

2. 위, 아래, 좌, 우 백트래킹

3. 동전은 하나만 떨어뜨려야된다.

4. 동전 떨어뜨릴 수 없거나 버튼을 10번보다 많이눌러야되면 -1출력.(개인적으로 이게제일 어려웠다.)

 

 

1. 두 동전의 위치

입력으로 o가 들어올때마다 coinLocation변수에 2차원 배열로 저장했다.

 

2. 위, 아래, 좌, 우 백트래킹

처음에는 하나씩하려다가 어차피 두 동전이 동시에 이동하니까 굳이 하나씩할 필요도없고 해봤자 안될거같아서 동시에 이동했다.

나는 떨어뜨리는걸 알기위해서 동전이 떨어지는 모서리지점에 x로 도배를 해놨다.

이 부분인데 무슨말인지 모른다면 아래그림을 보면된다.

for _ in 0...m + 1{
    arr[0].append("x")
}
for i in 1...n{
    arr[i].append("x")
    for j in (readLine()!.map{String($0)}) {
        arr[i].append(j)
        if j == "o"{
            coinLocation.append((i, arr[i].count - 1)) //코인위치 저장
        }
    }
    arr[i].append("x")
}
for _ in 0...m + 1{
    arr[n + 1].append("x")
}

백트래킹을 하면서 두 코인이 동시에 x를 만난다면 그건 같이 떨어진거니까 continue로 패스해준다.

그리고 한쪽만 x를 만난다면 그건 하나만 떨어진거니까 result에 저장해준다.

 if arr[nx1][ny1] == "x" && arr[nx2][ny2] == "x"{
            continue
        }else if arr[nx1][ny1] == "x"{
            result = min(result, depth)
//            print(result)
        }else if arr[nx2][ny2] == "x"{
            result = min(result, depth)
//            print(result)
        }

난잡한 코드의 끝판왕이다.

이동하는 위치가 범위안에 맞게 들어오는지 확인하고 방문여부 확인하고 x에 들어가버리면 안되니까 좌표가 x에 들어가는건지도 확인해준다.

그리고 벽에 들어가면 안되니까

벽에 둘다 안들어간경우

벽에 둘다 들어간경우

벽에 한개만 들어간경우를 처리해준다.

벽에 한개만 들어간경우에서 벽에 들어간다는건 벽에 막혀서 못간다는 의미이다.

못가게되면 좌표를 제자리에두면된다.

if nx1 >= 0 && nx1 < n + 2 && ny1 >= 0 && ny1 < m + 2 && !visited1[nx1][ny1] && nx2 >= 0 && nx2 < n + 2 && ny2 >= 0 && ny2 < m + 2 && !visited2[nx2][ny2] && arr[nx1][ny1] != "x" && arr[nx2][ny2] != "x"{
            if arr[nx1][ny1] != "#" && arr[nx2][ny2] != "#"{
                visited1[nx1][ny1] = true
                visited2[nx2][ny2] = true
                dfs(depth + 1, nx1, ny1, nx2, ny2)
                visited1[nx1][ny1] = false
                visited2[nx2][ny2] = false
            }else if arr[nx1][ny1] == "#" && arr[nx2][ny2] == "#"{
                visited1[nx1][ny1] = true
                visited2[nx2][ny2] = true
                dfs(depth + 1, x1, y1, x2, y2)
                visited1[nx1][ny1] = false
                visited2[nx2][ny2] = false
            }else if arr[nx1][ny1] == "#"{
                visited2[nx2][ny2] = true
                dfs(depth + 1, x1, y1, nx2, ny2)
                visited2[nx2][ny2] = false
            }else if arr[nx2][ny2] == "#"{
                visited1[nx1][ny1] = true
                dfs(depth + 1, nx1, ny1, x2, y2)
                visited1[nx1][ny1] = false
            }
        }
    }

 

4.

내가 현재 갖고있는 최소움직임보다 depth가 크면 어차피 최소움직임이 될 수 없으니까 돌지않는다. 그냥리턴

그리고 depth가 10보다 클때는 내가 현재 갖고있는 최소움직임(result)와 비교해서 최소값을 result에 넣어준다.

이유는 depth가 10보다 크더라도 내가 현재 갖고있는 최소움직임과 비교를 해줘서 현재 갖고있는 최소움직임이 없는경우에는 10이넘는 depth값을 result에 저장해두고 전체코드의 맨 아래를 보면 result가 10보다 클 때 -1을 출력해준다.

참고로 두 동전을 떨어뜨릴 수 없을경우에는 result에 값이 안들어가서 Int.max일거니까 따로 처리안해줘도 위에서 해준 처리로 처리가된다.

if result < depth {//
        return
    }
if depth > 10 {//
        result = min(result, depth)
        return
}

 

후기 : 코드가 아주 난잡하다.. 다른사람들은 방문처리 안하는거같은데 나만한건가..?

이런저런조건맞추면서 백트래킹하니까 푸는 시간이 너무 오래걸렸다.

import Foundation
let nm = readLine()!.split(separator: " ").map{Int(String($0))!}
let n = nm[0]
let m = nm[1]
var arr = Array(repeating: [String](), count: n + 2)
var coinLocation = [(Int,Int)]() //동전의 위치 저장
let dx = [-1, 1, 0, 0]
let dy = [0, 0, -1, 1]
var visited1 = Array(repeating: Array(repeating: false, count: m + 3), count: n + 3)
var visited2 = Array(repeating: Array(repeating: false, count: m + 3), count: n + 3)
var result = Int.max
for _ in 0...m + 1{
    arr[0].append("x")
}
for i in 1...n{
    arr[i].append("x")
    for j in (readLine()!.map{String($0)}) {
        arr[i].append(j)
        if j == "o"{
            coinLocation.append((i, arr[i].count - 1)) //코인위치 저장
        }
    }
    arr[i].append("x")
}
for _ in 0...m + 1{
    arr[n + 1].append("x")
}

//print(arr)
func dfs(_ depth: Int, _ x1: Int, _ y1: Int, _ x2: Int, _ y2: Int){

    if result < depth {//
        return
    }
    if depth > 10 {//
        result = min(result, depth)
        return
    }

    for i in 0..<4{
        let nx1 = x1 + dx[i]
        let ny1 = y1 + dy[i]

        let nx2 = x2 + dx[i]
        let ny2 = y2 + dy[i]

        if arr[nx1][ny1] == "x" && arr[nx2][ny2] == "x"{
            continue
        }else if arr[nx1][ny1] == "x"{
            result = min(result, depth)
//            print(result)
        }else if arr[nx2][ny2] == "x"{
            result = min(result, depth)
//            print(result)
        }
        if nx1 >= 0 && nx1 < n + 2 && ny1 >= 0 && ny1 < m + 2 && !visited1[nx1][ny1] && nx2 >= 0 && nx2 < n + 2 && ny2 >= 0 && ny2 < m + 2 && !visited2[nx2][ny2] && arr[nx1][ny1] != "x" && arr[nx2][ny2] != "x"{
            if arr[nx1][ny1] != "#" && arr[nx2][ny2] != "#"{
                visited1[nx1][ny1] = true
                visited2[nx2][ny2] = true
                dfs(depth + 1, nx1, ny1, nx2, ny2)
                visited1[nx1][ny1] = false
                visited2[nx2][ny2] = false
            }else if arr[nx1][ny1] == "#" && arr[nx2][ny2] == "#"{
                visited1[nx1][ny1] = true
                visited2[nx2][ny2] = true
                dfs(depth + 1, x1, y1, x2, y2)
                visited1[nx1][ny1] = false
                visited2[nx2][ny2] = false
            }else if arr[nx1][ny1] == "#"{
                visited2[nx2][ny2] = true
                dfs(depth + 1, x1, y1, nx2, ny2)
                visited2[nx2][ny2] = false
            }else if arr[nx2][ny2] == "#"{
                visited1[nx1][ny1] = true
                dfs(depth + 1, nx1, ny1, x2, y2)
                visited1[nx1][ny1] = false
            }
        }
    }
}
dfs(1, coinLocation[0].0, coinLocation[0].1, coinLocation[1].0, coinLocation[1].1)

if result > 10 {
    print(-1)
}else{
    print(result)
}