[알고리즘문제] 릿코드 Rotting Oranges

leetcode.com/problems/rotting-oranges/

Rotting Oranges - LeetCode

2차원 배열에 오렌지가 담겨져 있다고 가정한다.

오렌지의 상태는 없는경우, 그냥 오렌지, 썩은 오렌지 요렇게 3개의 상태가 된다.

2차원 배열 내 썩은 오렌지가 있을 경우 1분마다 해당 오렌지를 기준으로 4방향으로 인접한 오렌지가 썩는다.

2차원 배열 내 오렌지들이 모두 썩을때 까지의 시간을 계산해야 된다.

만약 모든 오렌지를 썩힐 수 없을 경우 -1을 return한다.

#include<iostream>
#include<vector>
#include<queue>

using namespace std;


//Input: 
//  2차원 배열 grid를 넣을 경우
//  [2, 1, 1],
//  [1, 1, 0],
//  [0, 1, 1]
//Output: 4
//Constraints :
// 1) m이 grid.length이고, n이 grid[i].length일 경우
//     1 <=m, n <= 10
// 2) grid[i][j]는 0, 1, 2의 값만 들어온다,
//Edge Case :
//brute force : naive
//  BFS풀이
//  time : O(3n^2)
//  space : O(n^2)
//code
class Solution {
private:
    queue<pair<int, int>> q;
public:
    int orangesRotting(vector<vector<int>>& grid) {
        int min = 0;
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[i].size(); j++) {
                if (grid[i][j] == 2) {
                    q.push(pair<int, int>(i, j));
                }
            }
        }

        while (!q.empty()) {
            int loop = q.size();
            for (int i = 0; i < loop; i++){
                grid = change(grid, pair<int, int>(q.front().first, q.front().second));
                q.pop();
            }
            min++;
        }

        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[i].size(); j++) {
                if (grid[i][j] == 1) {
                    return -1;
                }
            }
        }
        if (min != 0) min--;
        return min;
    }
    vector<vector<int>> change(vector<vector<int>>& grid, pair<int, int> pos) {
        //4방향으로 해당 값이 1이면 2로 값 변경
        //상
        if (pos.first > 0) {
            if (grid[pos.first - 1][pos.second] == 1) {
                grid[pos.first - 1][pos.second] = 2;
                q.push(pair<int, int>(pos.first - 1, pos.second));
            }
        }
        //하
        if (pos.first < grid.size() - 1) {
            if (grid[pos.first + 1][pos.second] == 1) {
                grid[pos.first + 1][pos.second] = 2;
                q.push(pair<int, int>(pos.first + 1, pos.second));
            }
        }
        //좌
        if (pos.second > 0) {
            if (grid[pos.first][pos.second - 1] == 1) {
                grid[pos.first][pos.second - 1] = 2;
                q.push(pair<int, int>(pos.first, pos.second - 1));
            }
        }
        //우
        if (pos.second < grid[pos.first].size() - 1) {
            if (grid[pos.first][pos.second + 1] == 1) {
                grid[pos.first][pos.second + 1] = 2;
                q.push(pair<int, int>(pos.first, pos.second + 1));
            }
        }
        return grid;
    }
};

pair<int, int>형 q를 선언하여 2차원 배열 grid의 원소 중 2인 원소의 위치값을 q에 push해둔다.

1. q가 비어있지 않는 동안 반복한다.

2. q의 크기만큼 q에 들어있는 위치값을 이용하여 해당 위치값의 상하좌우의 위치를 검증(가장자리인지 확인) 후

상하좌우의 값이 1일 경우 2로 변경 후 q에 push 하는 작업을 반복한다.

3. q를 한번 pop한다.

4. min을 증가시킨다.

5. grid에 1이 있는지 검증하여 존재할 경우 -1을 return시킨다.

6. 마지막에 min을 한번 감소 시킨 후 return하는 이유는 q의 마지막에 push된 값은 더이상 확산할 수 없는 마지막 상태이므로(1분 전에 요구사항이 완료 된 상태) min을 한번 감소해주어야 한다. 

 

 

rust로 작성한 코드

use std::collections::VecDeque;

struct Solution;

impl Solution {
    pub fn oranges_rotting(mut grid: Vec<Vec<i32>>) -> i32 {
        let mut q : VecDeque<(i32, i32)> = VecDeque::new();
        let mut _loop : i32 = 0;
        //println!("0 번째");
        for i in 0..grid.len(){
            for j in 0..grid[i].len(){
                //print!("{} ", grid[i][j]);
                if grid[i][j] == 2{
                    q.push_back((i as i32, j as i32));
                    _loop += 1;
                }
            }
            //println!();
        }
        let mut min : i32 = 0;
        while !q.is_empty() {
            let mut tmp  = vec![];
            //println!("{} 번째", min + 1);
            while let Some(p) = q.pop_front() {
                let t = [p.0 as usize, p.1 as usize];
                if t[0] > 0 && grid[t[0] - 1][t[1]] == 1{
                    grid[t[0] - 1][t[1]] = 2;
                    tmp.push((p.0 - 1, p.1));
                }
                if t[0] < grid.len() - 1 && grid[t[0] + 1][t[1]] == 1{
                    grid[t[0] + 1][t[1]] = 2;
                    tmp.push((p.0 + 1, p.1));
                }
                if t[1] > 0 && grid[t[0]][t[1] - 1] == 1{
                    grid[t[0]][t[1] - 1] = 2;
                    tmp.push((p.0, p.1 - 1));
                }
                if t[1] < grid[t[0]].len() - 1 && grid[t[0]][t[1] + 1] == 1{
                    grid[t[0]][t[1] + 1] = 2;
                    tmp.push((p.0, p.1 + 1));
                }
            };
            if !tmp.is_empty() {
                min += 1;
                //println!("{:?}", tmp);
                for p in tmp{
                    q.push_back(p)
                }
            }
        }
        for i in 0..grid.len() {
            for j in 0..grid[i].len(){
                if grid[i][j] == 1 {
                    return -1
                }
            }
        }
        min
    }
}
pub fn run(){

    let mut grid: Vec<Vec<i32>> = vec![
        vec![2, 1, 1],
        vec![1, 1, 0],
        vec![0, 1, 1]
    ];
    
    println!("{}", Solution::oranges_rotting(grid));
}