[백준/Swift] 1926번 : 그림

안녕하세요!!

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

1926번: 그림

 

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

도화지 (paper) 안에 그림은 1로 색칠된 부분입니다.

이 그림은 가로, 세로 (상 하 좌 우) 로 연결되어있고, 대각선 연결은 다른 그림으로 간주됩니다.

 

도화지의 모든 좌표를 탐색하면서, visited라는 배열을 통해 dfs 탐색을 하지 않은 좌표라면 그 좌표를 시작점으로 주변 그림의 크기를 측정해 나갔습니다.

 

저는 처음에 그림 크기 값들을 아래의 방식으로 배열에 추가를 하고, 출력을 했는데 런타임 에러가 발생했습니다.

var res = [Int]()

dfs 의 탐색 을 끝 낸 후
for y in 0..<nm[0]{
    for x in 0..<nm[1]{
        if !visited[y][x] && paper[y][x] == 1{
            visited[y][x] = true
            count += 1
            dfs(x,y, &count)
            res.append(count)
            count = 0
        }
    }
}

글자 개수를 res 배열에 append 후
이런식으로 출력을 했는데..
print(res.count)
print(res.sorted(by: >).first!)
런타임 에러가 났다.

 

그래서 간단히 비교를 통한 max, 와 draw 그림의 개수를 측정하는 변수를 선언해서 문제를 해결했습니다.

 

import Foundation

var nm = readLine()!.split(separator: " ").map{Int(String($0))!}
//특정 좌표를 기준으로 탐색할 수 있는 방향들
var direction = [(1,0),(-1,0),(0,1),(0,-1)]
var visited = Array(repeating: Array(repeating: false, count: nm[1]), count: nm[0])

// 도화지
var paper = Array(repeating: [Int](), count: nm[0])
for i in 0..<nm[0]{
    paper[i] = readLine()!.split(separator: " ").map{Int(String($0))!}
}
//그림 개수
var draw = 0
//가장 큰 그림
var max = 0
//도화지 탐색
for y in 0..<nm[0]{
    for x in 0..<nm[1]{
        if !visited[y][x] && paper[y][x] == 1{
            var count = 1
            visited[y][x] = true
            dfs(x,y, &count)
            if max < count {
                max = count
            }
            draw += 1
        }
    }
}


func dfs(_ x :Int, _ y :Int, _ cnt : inout Int){
    for i in direction {
        let nx = i.1 + x
        let ny = i.0 + y
        if ny < 0 || ny > nm[0] - 1 || nx < 0 || nx > nm[1] - 1 {
            continue
        }
        if !visited[ny][nx] && paper[ny][nx] == 1{
            visited[ny][nx] = true
            cnt += 1
            dfs(nx,ny, &cnt)
        }
    }
}
print(draw)
print(max)

 

Come to my Github

 

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

 

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