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

카테고리의 글 더보기

댓글 1

티스토리툴바