백준 14716번 Swift 알고리즘 연습 - 현수막_BFS

요즘 BFS 문제를 골라서 푸는 중인데... 내가 고른 문제들이 상당히 비슷한 유형인건지 원래 BFS 문제들의 유형이 이렇게 동일하게 출제되는건지 잘 모르겠다... ㅋㅋㅋ

그만큼 BFS, DFS 문제들은 유형이 정형화되어 있는 것 같다.

 

 

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

1. 다른 문제들과 비슷한 과정을 겪는다.
2. 우선 Graph를 그려주고, 움직일 수 있는 방향을 설정해준다.
3. 그 다음은 bfs 함수를 이중 for문으로 돌려서 완전탐색해주면 끝난다.
4. 이때 bfs의 경우는 현재 탐색하고 있는 tuple을 기준으로 동서남북 이동하여 아직 방문하지 않은 지역이었다면 0을 할당해준다.
5. 예제의 입력값을 예시로 들면, "A" "N" "T"가 Graph 상에 기록되어 있다.
6. 이때 A글자를 따라서 만들어져 있던 1들을 전부 0으로 만들어 놓고 다음 칸으로 이동하다보면 N을 만나게 되고 이때부터 또 1들을 전부 0으로 만든다... 이를 반복 하면 bfs가 종료된다. 

 

 

* 14716번

import Foundation

let input = readLine()!.split(separator: " ").map{ Int($0)! }
let m = input[0], n = input[1]
let d = [(-1,-1), (-1,1), (1,-1), (1,1), (-1,0), (1,0), (0,-1), (0,1)]

var count = 0
var graph = [[Int]]()

for _ in 0..<m {
    let row = readLine()!.split(separator: " ").map{ Int($0)! }
    graph.append(row)
}

for i in 0..<m {
    for j in 0..<n {
        if graph[i][j] == 1 {
            bfs(y: i, x: j)
            count += 1
        }
    }
}

print(count)

func bfs(y: Int, x: Int) {
    var queue = [(Int, Int)]()
    queue.append((y, x))
    graph[y][x] = 0

    while !queue.isEmpty {
        let point = queue.removeFirst()
        let y = point.0
        let x = point.1

        for (dy, dx) in d {
            let newY = y + dy
            let newX = x + dx
            if (0..<m).contains(newY) && (0..<n).contains(newX) && graph[newY][newX] == 1 {
                queue.append((newY, newX))
                graph[newY][newX] = 0
            }
        }
    }
}

 

 

정리(Today I Learned)

1. BFS 문제를 풀면서 조금 더 나에게 편한 코드를 찾고자 노력중이다. 예를 들면 위의 방향 설정 변수인 d의 경우 그냥 dx, dy로 나눠서 값을 보는 것이 내 눈에 훨씬 편하다. 또한 이 문제의 경우 x와 y의 좌표값을 바꿔서 사용했는데 아무래도 (x, y) 이 형태가 더 편한 것 같다. 마지막으로 이 문제의 경우 visited를 바로바로 graph에 표시할 수 있는 문제였지만... 아닌 문제들도 꽤 나오기 때문에 앞으로 는 시간에 영향을 많이 미치지 않는다면 visited 배열을 사용하여 방문/비방문 상태를 관리하는 것이 좋아보인다.