문제 링크 (opens new window)

풀이 (정답)

1. L ~ R 사이에 속하지 않는 블럭을 오버플로우 조건으로 설정하여 DFS
2. 평균값 계산 후 좌표 변경을 위해 좌표배열 마련하기

import Foundation

let nlr = readLine()!.split(separator: " ").map { Int($0)! }; let n = nlr[0]; let l = nlr[1]; let r = nlr[2]
var adj: [[Int]] = .init(repeating: [], count: n)
var visited: [[Bool]] = .init(repeating: .init(repeating: false, count: n), count: n)
let dy = [-1, 0, 1, 0]; let dx = [0, 1, 0, -1]
var ret = 0

// 연합 국가 수에 따른 인구수 변화가 없으면 무한루프 종료
var worldsChanged: Bool = true

// 묶인 국경별 평균 계산, dfs 돌면서 묶인 국경들 좌표 저장
var sumValue = 0; var pos: [(Int, Int)] = []

for i in 0..<n {
    adj[i] = readLine()!.split(separator: " ").map { Int($0)! }
}

func dfs(_ y: Int, _ x: Int) {
    visited[y][x] = true
    sumValue += adj[y][x]
    pos.append((y, x))

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

        if ny < 0 || nx < 0 || ny >= n || nx >= n || visited[ny][nx] {
            continue
        }

        if abs(adj[ny][nx] - adj[y][x]) < l || abs(adj[ny][nx] - adj[y][x]) > r {
            continue
        }

        dfs(ny, nx)
        worldsChanged = true
    }
}


while(worldsChanged) {
    visited = .init(repeating: .init(repeating: false, count: n), count: n)
    worldsChanged = false

    for i in 0..<n {
        for j in 0..<n {
            sumValue = 0
            pos = []

            if visited[i][j] { continue }
            dfs(i, j)

            for (y, x) in pos {
                adj[y][x] = Int(sumValue / pos.count)
            }
        }
    }
    if !worldsChanged { break }
    ret += 1
}

print(ret)

240717 재풀이

1. 반복문 탈출조건과 DFS를 도는 뼈대 풀이는 동일
2. 함수 파라미터에 배열의 주소값을 전달하여 Call by Reference로 풀이
3. 수행시간 반으로 줄어들었음

import Foundation

let NLR = readLine()!.split(separator: " ").map { Int($0)! }; let N = NLR[0]; let L = NLR[1]; let R = NLR[2]
var adj: [[Int]] = .init(repeating: .init(repeating: 0, count: N), count: N)
var visited: [[Bool]] = .init(repeating: .init(repeating: false, count: N), count: N)
let dy = [-1, 0, 1, 0]; let dx = [0, 1, 0, -1]
var day = 0

for i in 0..<N {
    adj[i] = readLine()!.split(separator: " ").map { Int($0)! }
}

// inout parameter - 배열 복사 X, 참조
func dfs(_ y: Int, _ x: Int, _ pos: inout [(Int, Int)]) {
    visited[y][x] = true

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

        if ny < 0 || nx < 0 || ny >= N || nx >= N || visited[ny][nx] {
            continue
        }

        if abs(adj[ny][nx] - adj[y][x]) >= L && abs(adj[ny][nx] - adj[y][x]) <= R {
            pos.append((ny, nx))
            dfs(ny, nx, &pos)
        } else {
            continue
        }
    }
}

while true {
    var flag = false
    visited = .init(repeating: .init(repeating: false, count: N), count: N)
    for i in 0..<N {
        for j in 0..<N {
            if visited[i][j] { continue }

            var pos = [(i, j)]
            dfs(i, j, &pos)

            if pos.count != 1 {
                flag = true

                var sum = 0
                for coord in pos {
                    sum += adj[coord.0][coord.1]
                }

                for coord in pos {
                    adj[coord.0][coord.1] = sum / pos.count
                }
            }
        }
    }

    if !flag { break }
    day += 1
}

print(day)