티스토리 뷰
문제
https://www.acmicpc.net/problem/2667
풀이
기본적인 BFS문제였다.
입력대로 house라는 변수를 만든 뒤에 반복문을 통해 1을 만났을때 bfs를 돌리도록 하였다. 그렇게되면 1을 만난 자리에서 dx,dy에 의해 상하좌우로 한칸씩 증가해가면서 1인 자리를 전부 찾게 될 것이고, 이때마다 area에 1을 더해주어 넓이를 구할 수 있게하였다.
또한, 하나의 단지를 다 탐색했다면 다음 탐색을 시작할때 for문을 통해 1을 찾게 될 것이므로 이때 count를 1 더해주어 총 단지 수를 계산하게 하였다.
import Foundation
let n = Int(readLine()!)!
var house: [[Int]] = []
let dx = [1,0,-1,0]
let dy = [0,1,0,-1]
var queue: [[Int]] = []
var count = 0
var result: [Int] = []
for _ in 0..<n {
house.append(readLine()!.map { Int(String($0))! })
}
for i in 0..<n {
for j in 0..<n {
if house[i][j] == 1 {
house[i][j] = 0
queue.append([i,j])
count += 1
var area = 0
while !queue.isEmpty {
let current = queue.removeFirst()
area += 1
for k in 0..<dx.count {
let newX = current[0] + dx[k]
let newY = current[1] + dy[k]
if newX < 0 || newY < 0 || newX >= n || newY >= n {
continue
}
if house[newX][newY] == 0 {
continue
}
queue.append([newX,newY])
house[newX][newY] = 0
}
}
result.append(area)
}
}
}
print(count)
for area in result.sorted(by: <) {
print(area)
}
_____________________________________________________________________________________________________
실버 BFS문제들은 풀이가 반복되는 문제들이 많다. 반복되더라도 많이 풀어본다면 코드의 구조를 완전 익힐 수 있을 것 같다.
근데 IDE를 안쓰고 코드를 작성하다보니 자꾸 짜잘한 실수들이 많이 나와서 더 꼼꼼해져야 할 것 같다.
또 문제에 오름차순 같은게 적혀있다면 까먹지말고 적용하기..
'PS' 카테고리의 다른 글
[Swift] 백준_안전 영역(2468) (1) | 2023.01.15 |
---|---|
[Swift] 백준_스타트링크(5014) (0) | 2023.01.15 |
[Swift] 백준_영역 구하기(2583) (0) | 2023.01.15 |
[Swift] 백준_불(5427) (0) | 2023.01.14 |
[Swift] 백준_SHOW ME THE DUNGEON(25330) (1) | 2023.01.14 |
댓글
최근에 올라온 글
- Total
- Today
- Yesterday