티스토리 뷰

문제

 

https://www.acmicpc.net/problem/2667

 

2667번: 단지번호붙이기

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여

www.acmicpc.net

 

 

풀이

 

기본적인 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