[백준 1743] 음식물 피하기 (Swift)

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

 

BFS

N*M 격자 판에 K개의 음식물의 위치가 (r,c) 로 주어지고, 인접한 음식들의 묶음 중 가장 큰 묶음의 크기를 출력하는 문제

(인접 : 상하좌우로 연결되어 있음)

 

접근방법

우선 2차원 배열 map에 음식물의 위치를 표시하고, map의 모든칸을 확인하면서 방문여부와 음식물여부를 확인해서,

방문한 적이 없고 음식물인 칸을 큐에 추가한다.

그럼 이제 이 칸이 속한 음식물 묶음의 크기를 BFS를 통해서 구한다. (인접한 음식물을 큐에 넣기, 큐가 빌 때까지 반복, 큐에서 뺄 때 마다 음식물 묶음의 크기 +1)

큐가 비어서 반복문이 종료되면 해당 음식물 묶음의 크기를 현재까지 최대 음식물 묶음의 크기를 저장하는 변수 result 와 비교해서

큰 값을 result에 담는다.

 

소스코드

import Foundation

func solution() -> Int {
    
    let dr = [-1,1,0,0]
    let dc = [0,0,1,-1]
    
    var result = 0
    // R C K
    let input = (readLine()?.split(separator: " ").map { Int($0)! })!
    let N = input[0]
    let M = input[1]
    let K = input[2]
    
    var map:[[Bool]] = [[Bool]](repeating: [Bool](repeating: false, count: M), count: N)
    for _ in 0..<K {
        let food = readLine()!.split(separator:" ").map { Int(String($0))! }
        map[food[0]-1][food[1]-1] = true
    }
    
    var visit:[[Bool]] = [[Bool]](repeating: [Bool](repeating: false, count: M), count: N)
    var q:[(Int, Int)] = []
    
    for r in 0..<N {
        for c in 0..<M {
            if map[r][c] && !visit[r][c] {
                q.append((r,c))
                visit[r][c] = true
                var cnt = 0
                while !q.isEmpty {
                    let now:(Int, Int) = q.removeFirst()
                    cnt += 1
                    for i in 0..<4 {
                        let nr = now.0+dr[i]
                        let nc = now.1+dc[i]
                        if nr >= 0 && nr < N && nc >= 0 && nc < M && !visit[nr][nc] && map[nr][nc] {
                            q.append((nr,nc))
                            visit[nr][nc] = true
                        }
                    }
                }
                result = max(cnt, result)
            }
        }
    }
    return result
}

print(solution())