6186 swift - Best Grass
2023. 2. 27. 01:59ㆍ🐣/BOJ
사용 알고리즘 BFS
[Swift] Breadth-First Search / BFS
BFS (Breadth-First Search) 인접한 노드를 먼저 탐색하는 방식. O(Vertex+Edge) A→B→C→D→E→F→G→H 해당하는 그래프는 아래와 같이 인접 리스트로 나타낼 수 있다. let graph: [String: [String]] = [ "A" : ["B", "C"],
chanhhh.tistory.com
사용 자료구조 Queue
[Swift] (자료구조) 큐 / Queue
import Foundation class Queue { var enQueue: [T] = [] var deQueue: [T] = [] var count: Int { return enQueue.count + deQueue.count } var isEmpty: Bool { return enQueue.isEmpty && deQueue.isEmpty } init() { } func push(_ element: T) { enQueue.append(element)
chanhhh.tistory.com
//
// 6186_Best Grass.swift
// swift_practise
//
// Created by Chan on 2023/02/27.
//
// https://www.acmicpc.net/problem/6186
//
// MARK: - BFS
typealias Coord = (r: Int, c: Int)
let d: [Coord] = [(-1, 0), (1, 0), (0, -1), (0, 1)]
let rc = readLine()!.split(separator: " ").map{Int(String($0))!}
let (R, C) = (rc[0], rc[1])
var count = 0
var map = [[String]]()
var vMap = Array(repeating: Array(repeating: false, count: C), count: R)
var q = Queue<(r: Int, c: Int)>()
for _ in 0..<R { map.append(readLine()!.map{String($0)}) }
func BFS(_ r: Int, _ c: Int) {
vMap[r][c] = true
while !q.isEmpty {
guard let dq = q.dequeue() else { continue }
for i in 0..<4 {
let nr = dq.r + d[i].r
let nc = dq.c + d[i].c
if nr >= 0 && nr < R && nc >= 0 && nc < C {
if map[nr][nc] == "#" && vMap[nr][nc] == false {
q.enqueue((nr, nc))
vMap[nr][nc] = true
}
}
}
}
}
for i in 0..<R {
for j in 0..<C {
if map[i][j] == "#" && vMap[i][j] == false {
count += 1
q.enqueue((i, j))
BFS(i, j)
}
}
}
print(count)
'🐣 > BOJ' 카테고리의 다른 글
| 9935 swift - 문자열 폭발 (0) | 2024.02.02 |
|---|---|
| 9663 swift - N-Queen (0) | 2023.06.12 |
| 11444 swift - 피보나치 수 6 (0) | 2023.06.11 |
| 11521 swift - Boggle (0) | 2023.04.05 |
| 9019 swift - DSLR (0) | 2023.03.03 |