[Swift] 2234 성곽 (BFS)

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

2234번: 성곽

 

생각

[ struct wall ]

wall은 벽에대한 정보보다는 그 위치의 대한 정보라서

- 위치 r, c

- 동서남북 벽의 유무

- 방의 번호 : 벽을 허물었을 때 현재 방의 넓이를 알 수 있도록

로 선언하였다.

 

c++ 로 풀 때는 << 로 비트로 풀었지만, Swift에서 비트는 아직 어색하고 잘 모르기 때문에

init 함수에서 직접 나눠주면서 벽의 유무를 설정해주었다.

 

[ BFS ]

그리고 방문하지 않은 곳이라면 bfs로 돌면서 방의 번호를 설정하고 방의 넓이를 구해서 저장해놓았다.

 

[ getLargeAreaWithRemoveWall ]

원래 BFS 하나 더 만들어서 구했다가 시간초과가 나서 (이 원인은 아니다)

삼중 for문으로 바꿔서 다음 위치가 다른 방 번호면 두개의 방 넓이를 더해주었다.

 

 

 

새벽에 문제가 잘풀릴 것 같아서 풀었다가 bfs를 오랜만에 풀어서 진짜 호되게~당했다..

혼자서 struct 만들고 어렵게 푼거같기도..

 

시간초과가 났었던 이유는, bfs 함수에서

visited 변수를 queue 에 넣을 때 true로 바꿔주지 않고

queue에서 뺐을 때 true로 바꿔주기 때문이었다.

 

 

import Foundation

// input: M, N
var input = readLine()!.split(separator: " ").map{ Int($0)! }
let N = input[0]
let M = input[1]

// 위치에 대한 정보
struct wall {
    var r: Int = 0
    var c: Int = 0
    var east: Bool = false
    var west: Bool = false
    var south: Bool = false
    var north: Bool = false
    var roomNum: Int = -1
    
    // 2로 나눠서 벽이 있는지 확인 후에 벽 설정
    init(_ r: Int, _ c: Int, _ info: Int) {
        self.r = r
        self.c = c
        
        var num = info, count = 0
        if info == 0 {
            return
        }
        while count < 4 {
            if num == 1 {
                setDirection(count, 1)
                break
            }
            setDirection(count, num % 2)
            num = num / 2
            count += 1
        }
    }
    
    mutating func setDirection(_ count: Int, _ val: Int) {
        let isWall = val == 1 ? true : false
        switch count {
        case 0: west = isWall
        case 1: north = isWall
        case 2: east = isWall
        case 3: south = isWall
        default: break
        }
    }
    
    // 벽이 있는지 확인
    func isWall(_ direction: Int) -> Bool {
        switch direction {
        case 0: return west
        case 1: return north
        case 2: return east
        case 3: return south
        default: break
        }
        return false
    }
}

// MARK: - 변수
// 성벽
var walls = [[wall]](Array(repeating: Array(repeating: wall(0, 0, 0), count: N), count: M))
// 탐색을 위한 visited 변수
var visited = [[Bool]](Array(repeating: Array(repeating: false, count: N), count: M))
// 방의 갯수, 넓은 방의 넓이, 벽 제거 후 넓은 방의 넓이
var roomCount = 0, largeArea = 0, largeAreaWithReomveWall = 0

// 방의 넓이 저장 roomCount로
var roomArea = [Int](Array(repeating: 0, count: N*M))

// west, north, east, south
let dr = [0, -1, 0, 1]
let dc = [-1, 0, 1, 0]


// input
for i in 0..<M {
    input = readLine()!.split(separator: " ").map{ Int($0)! }
    for j in 0..<N {
        walls[i][j] = wall(i, j, input[j])
    }
}

// MARK: - 함수
// 범위
func isIn(_ r: Int, _ c: Int) -> Bool {
    return 0<=r && r<M && 0<=c && c<N
}

// 탐색
func bfs(_ startR: Int, _ startC: Int) {
    var area = 0, nr = 0, nc = 0
    // queue라고 생각
    var queue = [wall]()
    
    queue.append(walls[startR][startC])
    visited[startR][startC] = true
    
    while !queue.isEmpty {
        let curWall = queue.first!
        walls[curWall.r][curWall.c].roomNum = roomCount
        area += 1
        queue.removeFirst()
        
        for i in 0..<4 {
            nr = curWall.r + dr[i]
            nc = curWall.c + dc[i]
            if isIn(nr, nc) && !visited[nr][nc] && !curWall.isWall(i) {
                visited[nr][nc] = true
                queue.append(walls[nr][nc])
            }
        }
    }
    roomArea[roomCount] = area
    largeArea = max(area, largeArea)
}

func getLargeAreaWithRemoveWall() {
    var nr = 0, nc = 0
    for i in 0..<M {
        for j in 0..<N {
            for k in 0..<3 {
                nr = walls[i][j].r + dr[k]
                nc = walls[i][j].c + dc[k]
                if isIn(nr, nc) && walls[i][j].roomNum != walls[nr][nc].roomNum {
                    largeAreaWithReomveWall = max(largeAreaWithReomveWall,
                                                  roomArea[walls[i][j].roomNum] +
                                                  roomArea[walls[nr][nc].roomNum])
                }
            }
        }
    }
}

// main
for i in 0..<M {
    for j in 0..<N {
        if !visited[i][j] {
            bfs(i, j)
            roomCount += 1
            
        }
    }
}

getLargeAreaWithRemoveWall()

print(roomCount)
print(largeArea)
print(largeAreaWithReomveWall)

개길다