백준 3019 빵집

출처: www.acmicpc.net/problem/3109

분류: 그리디, DFS

---

접근방식

첫번째 열부터 차례대로 연결할 수 있는지 탐색하면 되는 문제입니다. 

처음에 그냥 풀었다가 시간초과가 나고.. dfs를 사용해서 풀었는데,

주의할 건, 다음으로 연결할 수 있는 경우는 오른쪽, 오른쪽 위, 오른쪽 아래 3가지라서

다음 경우까지 모두 해봐야 하기 때문에 dfs에서 결과를 그냥 리턴하면 안되고 true일 경우에만 리턴해야 합니다.

해결방법

let n = readLine()!.split(separator: " ").map{Int($0)!}
var map = [[Bool]]()

for _ in 0..<n[0] {
  // "." 이면 true, "X" 이면 false
  map.append(readLine()!.map {$0 == "."})
}

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

func dfs(_ r: Int, _ c: Int) -> Bool {
  
  
  if c == n[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
      // return dfs(row, col)처럼 그냥 리턴시켜버리면 안된다.
      // 결과가 true일 경우에만 true를 리턴해야한다.
      // 아니면 다음 경우를 해보기 위해 통과시켜야 함
      if dfs(row, col) {
        return true
      }
    }
  }
  return false
}

for i in 0..<n[0] {
  if dfs(i, 0) { result += 1 }
}
//map.forEach{print($0)}
print(result)

 

배운점

dfs나 bfs 같은 전형적인 탐색 문제인데 왜 이걸 냅두고 자꼬 근본없는 코드를 ~~~~~~

dis, bfs에 익숙해지자!!