[BFS] 음식물 피하기 - baekjoon Swift

문제 : https://www.acmicpc.net/problem/1743

1743번: 음식물 피하기

 

풀이방법

1. 일단 주어진 input으로 맵을 만든다.
2. 맵 전체를 돌면서 만약 map[row][col] == 1 인지 찾는다. 즉 음식물이 있는지 찾는다.
3. 음식물이 있으면 BFS를 돌려서 상하좌우에 있는 음식물들을 찾아서 갯수를 알아낸다.
4. 방문한 곳은 map[row][col] = 0 으로 바꿔준다. 즉 음식물을 치워준다.

 

코드

import Foundation

let input = readLine()!.split(separator: " ").map{Int(String($0))!}
var map = Array(repeating: Array(repeating: 0, count: input[1]), count: input[0])
var result = 0

for _ in 0..<input[2] {
    let point = readLine()!.split(separator: " ").map{Int(String($0))!}
    points.append((col: point[1]-1,row: point[0]-1))
    map[point[0]-1][point[1]-1] = 1
}

func bfs(col: Int, row: Int) -> Int {
    var count = 0
    var queue = [(Int, Int)]()
    queue.append((row, col))
    
    while !queue.isEmpty {
        let dot = queue.removeFirst()
     
            count += 1
            for n in [(dot.0+1, dot.1),(dot.0-1, dot.1), (dot.0, dot.1+1), (dot.0, dot.1-1)] {
                if n.0 >= 0 && n.0 < map.count && n.1 >= 0 && n.1 < map[0].count && map[n.0][n.1] == 1 {
                    queue.append(n)
                    map[n.0][n.1] = 0
                }
            }
        }
    
    return count
}


for i in 0..<map.count {
    for j in 0..<map[0].count {
        if map[i][j] == 1 {
            map[i][j] = 0
            result = max(bfs(col: j, row: i), result)
        }
        
    }
}

print(result)