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

💻 문제 링크

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

7576번: 토마토

 

💻 풀이

BFS로 풀었다. 사실 시작점이 여러개인 BFS는 어떻게 풀어야할지 모르겠어서, 인터넷을 참고해서 풀었다ㅠㅠ 

1. m과 n을 입력받는다. 
2. 0, -1, 1이 들어있는 배열을 box로 입력받았다.
3. day는 며칠이 지났는지 판단하기 위해서 만든배열이다. 뒤에서 보면 한칸한칸 익어나갈때마다 +1 을 해준다.

let mn = readLine()!.split(separator: " ").map { Int(String($0))! }
let m = mn[0]
let n = mn[1]

var box = [[Int]]()
for _ in 0..<mn[1] {
    let temp = readLine()!.split(separator: " ").map{Int(String($0))!}
    box.append(temp)
}

var day = Array(repeating: Array(repeating: 0, count: 1001), count: 1001)

 

1. dx, dy 상하좌우로 방향키를 설정했다.
2. queue를 사용해서 bfs로 돌려줄 것이다.
3. lastIdx는 입력받는 이유가, 가장 마지막에 방문한 idx인경우, 마지막 날 방문한 인덱스라는 의미이므로, 저장해두었다가 마지막에 출력할 때 사용해줄 것이다.
4. idx는 0부터 시작한다. 원래 removeFirst를 사용해서 queue에 pop해서 넣어주려고 했는데, 이렇게 하게되면 시간초과가 날 확률이 커서 idx를 사용해본다.
5. isCooked 익은 토마토가 있냐 없냐를 따질때 사용할 것이다.

let dx = [0, 0, -1, 1]
let dy = [-1, 1, 0, 0]

var queue = [[Int]]()
var lastIdx = [0, 0]
var idx = 0
var isCooked = true

 

 

1. 먼저 queue에다가 익은 토마토들을 넣어준다. 이 과정이 조금 헷갈렸는데, 시작점이 여러개이므로 여러개 넣고 시작해주면 된다고 이해하자.

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

 

1. bfs함수를 만든다.
2. bfs함수에서는 queue의 수보다, 인덱스 수가 더 작을때까지 돌린다.

func bfs() {
    while idx < queue.count {
        let pop = queue[idx]
        idx += 1

        for k in 0..<4 {
            let nx = pop[0] + dx[k]
            let ny = pop[1] + dy[k]
            
            if nx >= 0 && nx < n && ny >= 0 && ny < m {
                if box[nx][ny] == 0 {
                    box[nx][ny] = 1
                    queue.append([nx, ny])
                    day[nx][ny] = day[pop[0]][pop[1]] + 1
                    lastIdx = [nx, ny]
                }
            }
        }
    }
}

bfs()

 

1. 여기서중요했던 개념, 익은 토마토가 하나라도 있으면 안되기 때문에 익었는지 판별한 후에 출력해준다.

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

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

 

💻 소스코드 

https://github.com/deslog/Algorithm/blob/main/Algorithm/Boj/7576_%ED%86%A0%EB%A7%88%ED%86%A0/main.swift

GitHub - deslog/Algorithm

let mn = readLine()!.split(separator: " ").map { Int(String($0))! }
let m = mn[0]
let n = mn[1]
var box = [[Int]]()
var day = Array(repeating: Array(repeating: 0, count: 1001), count: 1001)

for _ in 0..<mn[1] {
    let temp = readLine()!.split(separator: " ").map{Int(String($0))!}
    box.append(temp)
}

let dx = [0, 0, -1, 1]
let dy = [-1, 1, 0, 0]

var queue = [[Int]]()
var lastIdx = [0, 0]
var idx = 0
var isCooked = true

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

func bfs() {
    while idx < queue.count {
        let pop = queue[idx]
        idx += 1

        for k in 0..<4 {
            let nx = pop[0] + dx[k]
            let ny = pop[1] + dy[k]
            
            if nx >= 0 && nx < n && ny >= 0 && ny < m {
                if box[nx][ny] == 0 {
                    box[nx][ny] = 1
                    queue.append([nx, ny])
                    day[nx][ny] = day[pop[0]][pop[1]] + 1
                    lastIdx = [nx, ny]
                }
            }
        }
    }
}

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

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