(Swift) [백준/Boj] 1743번 : 음식물 피하기

1743: 음식물 피하기 링크

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

1743번: 음식물 피하기

난이도 : Silver 1

 

유형 : DFS

 

 

#접근방식 및 중요포인트

• Dfs를 돌면서 상,하,좌,우로 음식물은 발견하면, 카운팅을 해준다. 그리고 더 이상 탐색할 경로가 없다면 그 값을 임시저장해놓는다.
• 그리고 저장한 값들에서 가장 큰 값을 찾아 출력해준다.

Swift

import Foundation

let input_ = Array(readLine()!.split(separator: " ").map{Int($0)!})
var n = input_[0], m = input_[1], k = input_[2]
var graph = Array(repeating: Array(repeating: 0, count: m), count: n)
var cnt = 0
var max_cnt = 0

func is_valid(x:Int , y:Int)->Bool{
    if x >= 0 , y >= 0, x < n, y < m{
        return true
    }
    return false
}

func dfs(x:Int, y:Int){
    if !is_valid(x: x, y: y){
        return
    }
    if graph[x][y] == 1 {
        graph[x][y] = 0
        dfs(x: x, y: y-1)
        dfs(x: x, y: y+1)
        dfs(x: x+1, y: y)
        dfs(x: x-1, y: y)
        cnt += 1
        return
    }
    return
}

for _ in 1...k{
    let xy = readLine()!.split(separator: " ").map{Int($0)!}
    let x = xy[0] - 1, y = xy[1] - 1
    graph[x][y] = 1
}

for x in 0...n-1{
    for y in 0...m-1{
        cnt = 0
        if graph[x][y] == 1{
            dfs(x: x,y: y)
            max_cnt = max(max_cnt, cnt)
        }
    }
}
print(max_cnt)