[백준/Swift] 2667번 : 단지번호붙이기 | bfs 문제 푸는 방법

안녕하세요

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

2667번: 단지번호붙이기

 

문제를 풀기 전에 간단하게 문제를 해석하면서 시작하겠습니다.

• 지도는 N * N 정사각형입니다.

• 지도 안 집이 있는 경우 1 과 집이 없는 경우 0 으로 지도가 구성 되어 있습니다.

• 집이 있는 경우에
• 좌, 우, 위, 아래로 다른 집(1 ) 이 연결된 경우, 단지를 정의 할 수 있습니다.

 

저는 이 문제를 해결하기 위해 지도 크기만큼의 visited : [[Bool]]함수를 정의했고,

특정 좌표 y, x 일때 visited[y][x] == false && map[y][x] == 1 // 특정 좌표를 방문하지 않았는가? && 그 좌표가 지도에서 1 (아파트) 인가? 조건을 걸은 후에

특정 좌표가 두 조건을 만족하면 해당 좌표를 시작점!!으로 bfs 탐색을 이어나갔습니다. 

 

이 문제의 경우, 특정 좌표를 기준으로 좌, 우, 위 ,아래를 탐색하는 4번의 포문을 통해,

특정좌표가 예를들어 4, 5인 경우, 

첫번째 포문의 경우, (5,5) 일때, 두번째 (3,5) 세번째 (4,6) 네번째 (4,4) 이렇게 4번의 경우를 탐색하면서 방문하지 않았고, 아파트(1)인 경우 계속 bfs를 호출하면서 , 단지 내 아파트를 카운트 하는 house 값을 1씩 증가시키면서 문제를 풀었습니다.

 

특정 좌표를 기준으로 첫 bfs 함수가 호출된 이후, 그 특정 좌표의 단지내 아파트들은 모두 탐색이 됬기에 res(결과)에 단지 내 아파트 수를 기록한 house값을 append했습니다.

 

다음은 코드입니다.

 

import Foundation

var N = Int(readLine()!)!
var direction = [(-1,0),(1,0),(0,1),(0,-1)]
//지도
var map = Array(repeating: [Int](), count: N)
//결과
var res = [Int]()

for i in 0..<N {
    map[i] = readLine()!.map{Int(String($0))!}
}
var visited = Array(repeating: Array(repeating: false, count: N), count: N)
/**
 * 단지내 아파트를 0,0부터 N,N까지 전부 탐색하는데,
 * 방문하지 않았으면서 && 아파트 인 경우
 * bfs 탐색을 했고, 그 결과값을 res 에 저장했습니다.
 */
for y in 0..<N{
    for x in 0..<N {
        var house = 0;
        if visited[y][x] == false && map[y][x] == 1{
            visited[y][x] = true;
            house += 1
            bfs(x,y, &house)
            res.append(house)
        }
    }
}
func bfs(_ x :Int, _ y:Int , _ house : inout Int){
    
    for i in direction {
        let nx = x + i.0
        let ny = y + i.1
        
        if nx < 0 || nx > N - 1 || ny < 0 || ny > N - 1 {
            continue
        }
        if visited[ny][nx] == false && map[ny][nx] == 1 {
            visited[ny][nx] = true
            house += 1
            bfs(nx, ny, &house)
        }
    }
}
print("\(res.count)")

res.sorted().forEach{print($0)}

 

 

Come to my Github

 

읽어주셔서 감사합니다!!

 

조언! 지적 정말 감사합니다.. 더 좋고 효율성있는 코드를 배우고 싶습니다.