백준 - 빵집(Swift)

백준 - 빵집(Swift)

 

 

 문제 설명

 

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

3109번: 빵집

 

 나의 풀이

 

첫번째로 가장 최대로 파이프라인을 까는 것은 그리디한 접근으로 맨 위부터 채우는 것이다. 

만약 오른쪽 위, 오른쪽, 오른쪽 아래의 길이 있을때 오른쪽 아래를 선택해서 파이프라인을 형성했다면 그 아래의 길들은 위쪽이 막혀서 설치할 경우의 수가 줄어들게 된다. 이 때문에 최대한으로 만들기 위해서는 오른쪽 위, 오른쪽, 오른쪽 아래로 순서대로 탐색해야 한다.

 

이 문제는 한번 지나간 길은 갈 수 없다는 점에서 일반적인 백트래킹을 사용하는 것이 아님을 알아야한다.

 

백트래킹의 정의는 특정한 조건을 만족하는 경우만 계속해서 탐색하는 것이다. 즉 가지치기를 하는 것인데 아래 코드에서는 특정 조건까지 도달하고, 특정 조건에 도달하지않으면 다른 경로로 가는(오른쪽 위가 막혀있다면 오른쪽으로) 것은 일반적인 백트래킹과 같다.

하지만 최종으로 원하는 특정 조건에 도달했을때(맨 끝에 도착) 이전것으로 돌아가서 다시 이어서 경로를 찾는 것이 아니다.

 

이 문제는 지나온 길에서는 관심이 없다. 반드시 처음가는 경로여야 하기 때문에 최종 조건에 도달한 순간 백트래킹을 하지않고 바로 끝낼 수 있어야한다. 그래서 dfs함수의 첫번째 조건에 끝에 도달했다면 true를 리턴하게 함으로써 모든 함수의 실행을 종료시킬 수 있게된다. 

그리고 if dfs(r, c)일때 true를 줌으로써 그 이후에 도달하지 못했을때는 그 단계에서 다시 오른쪽이나 오른쪽 아래로 갈 수 있게끔 설계를 한다.

 

import Foundation

let input = readLine()!.components(separatedBy:" ").map{Int($0)!}

var map = [[Bool]]()
for _ in 0..<input[0] {
    map.append(readLine()!.map{$0 == "."})
}

func inRange(_ r: Int, _ c: Int) -> Bool {
    return r>=0 && c>=0 && r<input[0] && c<input[1]
}

let dr = [-1, 0, 1]
var result = 0

func dfs(_ r: Int, _ c: Int) -> Bool {
    if c == input[1]-1 {
        return true
    }
    
    for i in 0..<3 {
        let row = r+dr[i]
        let col = c+1
        if inRange(row, col), map[row][col] {
            map[row][col] = false
            
            // 만약 다음 재귀로 들어간 것들이 막힌 곳이나 방문한 곳이 아니라면 true로
            if dfs(row, col) {
                return true
            }
        }
    }
    return false
}

for i in 0..<input[0] {
    if dfs(i, 0) {
        result += 1
    }
}
print(result)