[Swift][BFS] 백준 2234번 (성곽)

요구능력 : BFS

 

코드설명 : 

 

1) 이 성에 있는 방의 개수

BFS를 도는 횟수가 방의 개수가 되겠다.

BFS를 한번 돌게되면 벽에 막혀서 방문이 끝나게 된다.

방문하지 않은 곳의 배열을 모두 돌면서 방문처리를 해준다면 bfs를 도는 수 만큼이 방의 개수가 되겠다.

 

2) 가장 넓은 방의 넓이

큐에 append할 때 마다 방의 넓이는 count를 증가시켜줘야한다.

큐에 넣을때마다 증가시켜주지 않고 큐에 이동횟수를 붙여서 세게되면 모든 칸의 수를 다 세야하는데 아래와 같이 모든 경우의 수를 세지 못한다.

3) 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기

마찬가지로 2진수를 이용하여 있는 벽만 하나씩 지워보면서 arr을 전부 돌아보면된다.

 

후기 : 생각도 못한 &연산.. 비트연산문제를 한번도 안풀어봐서 어려웠던거같다..

비트연산공부해야지..

사실 다른 방법으로 풀어봤는데 1번과 2번요구사항은 구했으나 3번요구사항을 간단하게 구할방법이 없었다..

let nm = readLine()!.split(separator: " ").map{Int(String($0))!}
let n = nm[0]
let m = nm[1]
var arr = [[Int]]()
let dx = [0, -1, 0, 1]
let dy = [-1, 0, 1, 0]
var roomMaxSize = 0
var roomCount = 0
var visited = Array(repeating: Array(repeating: false, count: n), count: m)

for _ in 0..<m{
    arr.append(readLine()!.split(separator: " ").map{Int(String($0))!})
}

func bfs(_ startX: Int, _ startY: Int) -> Int{
    var queue = [(Int, Int)]()
    queue.append((startX, startY)) //x좌표, y좌표
    visited[startX][startY] = true
    var roomSize = 1

    while !queue.isEmpty{

        let pop = queue.removeFirst()
        var wall = 1
        let x = pop.0
        let y = pop.1


        for i in 0..<4{
            if (arr[x][y] & wall) != wall{
                let nx = x + dx[i]
                let ny = y + dy[i]

                if nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny]{
                    queue.append((nx, ny))
                    visited[nx][ny] = true
                    roomSize += 1
                }
            }
            wall = wall * 2
        }
        roomMaxSize = max(roomMaxSize, roomSize)
    }
    return roomMaxSize
}
for i in 0..<m{
    for j in 0..<n{
        if !visited[i][j]{

            bfs(i, j)
            roomCount += 1
        }

    }
}
print(roomCount)
print(roomMaxSize)
var biggerRoomMaxSize = 0

for i in 0..<m{
    for j in 0..<n{
        var k = 1
        while k <= 8{
            if arr[i][j] & k == k{
                visited = Array(repeating: Array(repeating: false, count: n), count: m)
                arr[i][j] -= k
                biggerRoomMaxSize = max(biggerRoomMaxSize, bfs(i, j))
                arr[i][j] += k
            }
            k = k * 2
        }
    }
}

print(biggerRoomMaxSize)