[백준] (Swift) 14716번 - 현수막 (실버1, DFS)

비슷한 유형의 문제가 돌려서 나온다는 말에 공감하는 요즘,,, 
더 다양한 유형의 문제를 풀어보기 위해서 노력해야겟다! 그리고 하루에 2문제만 푸는건 너무 적으니, 최소 3문제 이상은 풀어야겟다.
아좌좌 화이팅

 

⚫️ 문제

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

14716번: 현수막

⚫️ 나의 풀이

아니,,, 이코테 음료수 얼리기, 혹은 방금 전에 풀어본 백준 양문제... 등등 너무너무 비슷한 유형의 문제들이다. 이런 문제 유형은 정말 잘 풀수 잇을것같다는 자신감이 마구 샘솟는다. 이제 DFS 관련해서 다른 유형의 문제를 풀어봐야겠다.

문제를 보자마자, 그냥 DFS돌려서 글자가 있는 부분을 탐색해주는 방식을 생각햇다. 그리고 글자가 있는곳을 방문하면 전부 방문처리를 해줘버리는 것이지 ... 딱히 depth나 영역이 얼마나 커졌는지에 대한 처리가 필요하지 않은 간단한 문제다.

문제를 어떻게 풀었는지 그림으로 그려서 생각하는 습관을 형성하기 위해서 항상 아이패드를 가지고 다니면서 아래처럼 작성하고 코드를 작성한다. 이렇게 하게 되면 나중에 코드를 작성하면서 생각이 덜 꼬이는 것 같다.

 

⚫️ 정답코드

import Foundation

let mn = readLine()!.split(separator: " ").map{ Int($0)! }

var banner = [[Int]]()
for _ in 0..<mn[0] {
    banner.append(readLine()!.split(separator: " ").map{ Int($0)! })
}

var cnt = 0

// 방향키 : 상 하 좌 우 왼쪽위 왼쪽아래 오른쪽위 오른쪽아래
let dx = [-1, 1, 0, 0, -1, 1, -1, 1]
let dy = [0, 0, -1, 1, -1, -1, 1, 1]

private func dfs(x: Int, y: Int) {
    banner[x][y] = 0

    for i in 0..<8 {
        let nx = x + dx[i]
        let ny = y + dy[i]

        if nx < 0 || ny < 0 || nx >= mn[0] || ny >= mn[1] {
            continue
        }

        if banner[nx][ny] == 1 {
            dfs(x: nx, y: ny)
        }
    }
}

for i in 0..<mn[0] {
    for j in 0..<mn[1] {
        if banner[i][j] == 1 {
            cnt += 1
            dfs(x: i, y: j)
        }
    }
}

print(cnt)