[알고리즘/Swift] BOJ 1743 음식물 피하기 :: 그래프, DFS/BFS

Swift 로 풀어보는 그래프 문제입니다! 이번주에 Swift 스터디에서 그래프를 나가는데, 알고리즘 스터디에서도 그래프 문제풀이가 주제이네요 😀 개념과 문제를 동시에 접하니까 좋아요!

1743번: 음식물 피하기

 

👀 풀이 방법

입력으로 주어지는 좌표를 가지고 그래프(2차원 배열의 맵)을 만들 수 있어요! 좌표 (r, c) 는 2차원 배열에서 arr[r-1][c-1] 과 같이 접근할 수 있습니다. 

 

(문제가 좀 특이한데..) 통로에 떨어진 음식물 중 가장 큰 음식물의 크기를 구하는 문제입니다. 주변에 있는 음식물끼리는 뭉치게되어 크기가 커진다고 해요. 여기서 그래프의 구역을 나누는 알고리즘을 생각해낼 수 있습니다! 저는 이 과정에서 DFS 를 이용해 구역마다 라벨링을 했습니다.

 

BOJ 1743 

✔︎ Swift 코드

먼저, readLine() 함수를 통해 데이터 입력을 받고 그래프를 만들었습니다.

0 - 빈 통로, 1 - 음식물이 있는 통로

 

2차원 그래프를 반복하며 DFS 를 이용해서 그래프에서 인접된 음식물끼리 같은 라벨을 주는 라벨링 작업을 진행했어요. 라벨링 작업을 하면서, 인접한 좌표의 개수를 세어 반환합니다. 반복문에서는 반환된 값을 통해 최대 크기를 비교해주면 됩니다. 

예제 라벨링 전 / 후
1 0 0 0             2 0 0 0
0 1 1 0     ->     0 3 3 0
1 1 0 0              3 3 0 0

 

제출한 코드는 아래와 같습니다. 

import Foundation

// BOJ-1743 음식물피하기
func dfs(graph: inout [[Int]], y: Int, x : Int, label: Int) -> Int {
    // 그래프 범위를 벗어난 경우 종료
    if y < 0 || y >= graph.count || x < 0 || x >= graph[0].count {
        return 0
    }
    
    // 이미 라벨링이 되어있거나 0인 경우 종료
    if graph[y][x] != 1 {
        return 0
    }
    
    graph[y][x] = label // 라벨링
    
    // 상하좌우로 연결된 영역을 방문하며 개수를 센다.
    var count = 1
    count += dfs(graph: &graph, y: y-1, x: x, label: label)
    count += dfs(graph: &graph, y: y+1, x: x, label: label)
    count += dfs(graph: &graph, y: y, x: x-1, label: label)
    count += dfs(graph: &graph, y: y, x: x+1, label: label)
    return count
}

// Input
let line = readLine()!.split(separator: " ").map{Int($0)!}
var graph: [[Int]] = Array(repeating: Array(repeating: 0, count: line[1]), count: line[0])
for _ in 0..<line[2] {
    let coord = readLine()!.split(separator: " ").map{Int($0)!}
    graph[coord[0]-1][coord[1]-1] = 1
}

// Output
var label = 2
var max_size = 0
for y in 0..<line[0] {
    for x in 0..<line[1] {
        if graph[y][x] != 1 {
            continue
        }
        let size = dfs(graph: &graph, y: y, x: x, label: label)
        max_size = max(size, max_size)
        if size > 0 {
            label += 1
        }
    }
}
print(max_size)

---

Swift 를 통해 알고리즘 푸는게 마냥 어렵다고 생각했는데, 풀어보니 Swift 를 자주 쓸 수 있으니 더 익숙해지고 좋네요 🤩