백준 1941번 Swift 알고리즘 연습 - 소문난 칠공주_DFS

익숙해질만할 때 어려운 문제가 나왔다...!

이 문제는 고민을 거듭하다 결국 다른 분들의 코드를 많이 참고했는데 심지어 Swift로 된 코드는 없어서 Python 코드를 많이 참고했다..!

 

풀이를 보니 Combination, DFS+BFS, Backtracking 등등 다양한 개념을 혼합하여 사용해야했다.

어쩐지 BFS 하나로 안풀리더라니... 일단 기존에 풀어왔던 문제들과 제일 다른점은 현재 좌표에서 다음 좌표로 넘어갈 때 해당 지역의 값이 움직임에 영향을 전혀 미치지 않는다는 것이다. 즉, Y나 S에 상관없이 움직일 수 있었고 이때 이 모든 경로를 가능하게 하면 너무 많은 케이스가 발생하니 흔히 말하는 '가지치기'를 적용해야 했다.

 

그래서 dfs 함수를 사용할 때 Y가 4를 넘은 경우 바로 return을 시켜주었고, 그렇지 않은 경우에 한해서 학생이 7명이 모였다면 이 조합이 dfs 적으로 문제가 없는지 다시 한 번 체크하는 Check 함수를 넣어 이를 확인해주었다.

 

사실 코드는 짰지만... 이 문제 다시 나오면 당장 다시 못풀것 같다... 그래서 다음번 꼭 복습해야할 문제로 체크해두고자 한다.

 

 

이 문제를 풀면서 생각한 논리적 흐름은

1. 일단 7명의 사람이 모여야한다. 이렇게 모이는 경우의 수는 25C7로 볼 수 있는데
2. 이를 구하기 위해서 배열을 5X5 형태가 아닌 1차원 배열의 형태로 두고 경우의 수를 구해주는 것이 좋다.
3. 따라서 countY가 4이상 되지 않는 경우에 한해서 7명의 학생이 채워질때까지 dfs 함수를 돌린다.
4. 그리고 이때 count == 7을 만족시키는 케이스에 한하여 check 함수를 실행하는데 그 count 7이 dfs 적으로 문제가 없는지 확인한다.
5. dfs함수에서 7명의 학생을 고르는 방식은 Combination과 유사하기 때문에 dfs 적으로 맞지 않을 수가 있다.
6. 예를들면 대각선 방향으로 이어져 있다던지...
7. 따라서 dfs 적으로 문제가 없는 케이스를 찾기 위해 check 함수를 돌리고 문제가 없다면 visited 배열에도 방문 표시를 해준다.
8. 이렇게 되면 다음 번 count 7을 만족시키는 다른 케이스의 경우 check 함수를 돌릴때 이미 사용된 경로인지 아닌지 확인해줄 수 있다.

 

 

* 1941번

var arr: [String] = []

for _ in 0..<5 {
    arr.append(readLine()!)
}

let dx = [0, 0, 1, -1]
let dy = [1, -1, 0, 0]

var visited: [[Int]] = Array(repeating: Array(repeating: 0, count: 5), count: 5)
var ans = 0
var p: [Int] = []

func check(_ s: Int) {
    let x = s % 5
    let y = s / 5
    
    for i in 0..<4 {
        let newX = x + dx[i]
        let newY = y + dy[i]
        
        if newX >= 0 && newX < 5 && newY >= 0 && newY < 5 {
            if visited[newY][newX] == 0 {
                if p.contains(newY * 5 + newX) {
                    visited[newY][newX] = 1
                    check(newY * 5 + newX)
                }
            }
        }
    }
}

func dfs(_ count: Int, _ idx: Int, _ countY: Int) {
    if countY >= 4 || 25 - idx < 7 - count {
        return
    }
    
    if count == 7 {
        check(p[0])
        if visited.flatMap({$0}).reduce(0, +) == 7 {
            ans += 1
        }
        visited = Array(repeating: Array(repeating: 0, count: 5), count: 5)
        return
    }
    
    let x = idx % 5
    let y = idx / 5
    
    p.append(idx)
    
    if arr[y][arr[y].index(arr[y].startIndex, offsetBy: x)] == "Y" {
        dfs(count+1, idx+1, countY+1)
    } else {
        dfs(count+1, idx+1, countY)
    }
    
    p.removeLast()
    
    dfs(count, idx+1, countY)
}

dfs(0, 0, 0)
print(ans)

 

 

정리(Today I Learned)

1. 요즘 드는 생각은 이렇게 알고리즘 스터디를 시작해서 다행이라는 것. 혼자 알고리즘 문제를 풀었던 때가 있었는데 그땐 사실 아무 생각 없이 풀었다... 정말 구현적인 것만 신경을 썼었다. 그런데 스터디를 시작하며 어떤 알고리즘이 많이 기출되고, 시간 복잡도는 어떻게 계산해야하는지 등에 대한 고민을 하고 출발하는 것은 완전히 다른 것 같다. 지금이라도 이런 정석적인 방법을 따라 알고리즘 숙련도를 가파르게 올려야겠다.