[Swift][BFS] 백준 7576번 (토마토)

요구능력 : BFS에 대한 이해

 

코드설명 : 

 

이 문제의 핵심

1. 인접한 왼쪽, 오른쪽, 앞, 뒤 네방향에 있는 토마토에 영향을 준다.

2. 익은 토마토가 있는 지점부터 시작해야한다.(여러개가 있을경우 여러군데에서 시작한다. 예제3번 참조)

3. 토마토를 다익히지 못했을 경우를 생각해야한다.(예제2번같은경우)

4. 따로 Queue관련해서 지원되는게 없는 언어의 경우 시간초과에 유의한다.ㅠ

 

1. 1로 시작하는 시작지점들을 찾아서 Queue에 넣어둔다.

for i in 1...m{
    for j in 0..<n {
        if arr[i][j] == 1{
            queue.append((i, j))
        }
    }
}

 

 

2. 미리 선언해둔 idx를 queue의 수보다 적을때 까지 돌려준다.(idx가 0부터 시작하기 때문) 

이렇게 하면 removeLast()했을 때 보다 시간복잡도가 훨씬 좋아진다.

그리고 4방향을 탐색하면서 최소날짜를 구하기위해 현재 구하는 4방향의 pop좌표를 제공하는 depth에 1을 더해준다.(날짜가 하루 더해지는것)

lastIdx는 맨 마지막으로 방문하는 nx, ny가 가장 마지막날짜이기 때문에 사용했다.

func bfs(){
    while idx < queue.count{
        let pop = queue[idx]
        idx += 1
        for i in 0...3{
            let nx = pop.0 + dx[i]
            let ny = pop.1 + dy[i]
            
            if nx > 0 && nx <= m && ny >= 0 && ny < n{
                if arr[nx][ny] == 0{
                    arr[nx][ny] = 1
                    depth[nx][ny] = depth[pop.0][pop.1] + 1
                    queue.append((nx, ny))
                    lastIdx = (nx, ny)
                }
            }
        }
    }
}

3. isCooked를 통해 익지않은 토마토가 있는지 확인한다.

위에서 arr[nx][ny] = 1을 하여 방문하여 익힌 토마토들은 1처리를 해줬는데 여기서 1처리가 안되어 0으로 남아있는 토마토가 있다면 그 상자는 모두 익지않은 상태이기 때문에 -1을 출력해주기위해 isCooked를 false로 처리해준다.

for i in 1...m{
    for j in 0..<n{
        if arr[i][j] == 0 {
            isCooked = false
        }
    }
}

4. 토마토가 다익었다면 가장 마지막으로 익은 토마토까지의 날짜를 출력하고 다 익지않았다면 -1을 출력한다.

if isCooked{
    print(depth[lastIdx.0][lastIdx.1])
}else {
    print(-1)
}

 

후기 : 문제를 어느정도 다 풀었는데 모두익지못하는 상태를 찾지못했었다..

모두익지 않은 상태는 내가 익힌 토마토는 다 1로 바꿔놧던걸 생각못해서였던...😂

그리고 시간초과를 통해 Queue에서 시간초과를 줄이는 방법을 터득했다..!

진짜 좋은문제인듯...

let nm = readLine()!.split(separator: " ").map{Int(String($0))!}
let n = nm[0]
let m = nm[1]
var arr :[[Int]] = [[]]
var depth = Array(repeating: Array(repeating: 0, count: 1001), count: 1001)
var queue: [(Int, Int)] = []
var lastIdx = (0, 0)
var isCooked = true
var idx = 0
for _ in 1...m{
    arr.append(readLine()!.split(separator: " ").map{Int(String($0))!})
}

let dx = [-1, 1, 0, 0]
let dy = [0, 0, 1, -1]
for i in 1...m{
    for j in 0..<n {
        if arr[i][j] == 1{
            queue.append((i, j))
        }
    }
}

func bfs(){
    while idx < queue.count{
        let pop = queue[idx]
        idx += 1
        for i in 0...3{
            let nx = pop.0 + dx[i]
            let ny = pop.1 + dy[i]
            
            if nx > 0 && nx <= m && ny >= 0 && ny < n{
                if arr[nx][ny] == 0{
                    arr[nx][ny] = 1
                    depth[nx][ny] = depth[pop.0][pop.1] + 1
                    queue.append((nx, ny))
                    lastIdx = (nx, ny)
                }
            }
        }
    }
}

bfs()
for i in 1...m{
    for j in 0..<n{
        if arr[i][j] == 0 {
            isCooked = false
        }
    }
}

if isCooked{
    print(depth[lastIdx.0][lastIdx.1])
}else {
    print(-1)
}