[백준/Swift] 14716번 : 현수막

안녕하세요

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

14716번: 현수막

 

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

• 현수막을 필터링 했을 때!!

• 글자 == 1 아닌 경우 0 으로 되는 필터링이 있다고 합니다.

• 글자 1 은 상하, 좌우, 대각선으로 서로 인접해있는 경우 글자 한개로 측정됩니다.

글자의 개수가 몇개인지 구하는 문제입니다.

 

이 문제를 보고 주어진 문자는 그래프에서 특정 노드가 연결됬다고 생각해서 bfs 탐색을 통해 접근해 나아갔습니다.

여기서 주의할 점은 대각선까지 탐색범위에 포함된다는 것입니다.

 

import Foundation
//M = 세로, N = 가로
var MN = readLine()!.split(separator: " ").map{Int(String($0))!}
//주어진 현수막을 필터링한 값
var filter = Array(repeating: [Int](), count: MN[0])
//탐색 위치
var direction = [(1,0),(1,1),(1,-1),(0,1),(0,-1),(-1,0),(-1,-1),(-1,1)]
//방문 여부
var visited = Array(repeating: Array(repeating: false, count: MN[1]), count: MN[0])

for i in 0..<MN[0]{
    filter[i] = readLine()!.split(separator: " ").map{Int(String($0))!}
}
//단어 수
var word = 0;

for y in 0..<MN[0]{
    for x in 0..<MN[1]{
        if !visited[y][x] && filter[y][x] == 1 {
            visited[y][x] = true
            bfs(x,y)
            word += 1
        }
    }
}
func bfs (_ x :Int ,_ y : Int){
    for i in direction{
        let ny = i.0 + y
        let nx = i.1 + x
        if ny < 0 || ny > MN[0] - 1  || nx < 0 || nx > MN[1] - 1{
            continue
        }
        if !visited[ny][nx] && filter[ny][nx] == 1 {
            visited[ny][nx] = true
            bfs(nx, ny)
        }
    }
}
print(word)

 

이와 비슷한 문제는

<2667번 : 단지번호붙이기>

<4963번 : 섬의 개수> 

등이 있습니다.

 

Come to my Github

 

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

 

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