[백준 2667] 단지번호붙이기 (Rust 풀이; Silver I)

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

 

 이 블로그는 내가 공부한 것을 올리는 블로그고 나는 BFS 정도는 발가락으로도 짤 수 있기 때문에 자세한 풀이를 올리지는 않는다. 그런데 이 문제를 블로그에 올리기로 결심한 이유는 내가 지금 Rust를 공부하고 있기 때문이다. 그러니까 BFS가 어떻게 돌아가는지 알고리즘은 모두가 알고 있다고 가정하고 자세한 구현을 보자.

 

use std::collections::VecDeque;
use std::ops::Add;

#[derive(Clone)]
#[derive(Copy)]
struct Point {
    i: i32,
    j: i32,
}

impl Point {
    const fn new(i: i32, j: i32) -> Point {
        Point{i, j}
    }
}

impl Add for Point {
    type Output = Point;

    fn add(self, other: Point) -> Self::Output {
        Point{
            i: self.i + other.i,
            j: self.j + other.j,
        }
    }
}

fn main() {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    let n: usize = s.trim().parse().unwrap();

    let mut grid = Vec::<Vec<u8>>::with_capacity(n as usize);

    for _ in 0..n {
        let mut s = String::new();
        std::io::stdin().read_line(&mut s).unwrap();
        let to_push = Vec::from(s);
        grid.push(to_push);
    }

    let mut ret = Vec::new();

    let mut visited = vec![vec![0; n]; n];
    let mut queue = VecDeque::<Point>::new();

    for i in 0..n {
        for j in 0..n {
            if visited[i][j] == 0 && grid[i][j] == '1' as u8 {
                let p = Point::new(i as i32, j as i32);
                visited[i][j] = 1;
                queue.push_back(p);
                let size = bfs(&mut queue, &grid, &mut visited);
                ret.push(size);
            }
        }
    }

    ret.sort();
    println!("{}", ret.len());
    for x in ret {
        println!("{}", x);
    }
}

fn bfs(queue: &mut VecDeque<Point>,
       grid: &Vec<Vec<u8>>,
       visited: &mut Vec<Vec<i32>>) -> i32
{
    const DVS: [Point; 4] = [
        Point::new(0, 1),
        Point::new(0, -1),
        Point::new(1, 0),
        Point::new(-1, 0),
    ];

    let mut ret = 1;
    while !queue.is_empty() {
        let p = queue.front().unwrap().to_owned();
        let n = visited.len() as i32;
        queue.pop_front().unwrap();

        for dv in DVS {
            let next = p + dv;

            if next.i < 0 || next.i >= n || next.j < 0 || next.j >= n {
                continue
            }

            if grid[next.i as usize][next.j as usize] == '0' as u8 {
                continue
            }

            if visited[next.i as usize][next.j as usize] == 0 {
                visited[next.i as usize][next.j as usize] = 1;
                queue.push_back(next);
                ret += 1;
            }
        }
    }

    ret
}

Rust는 왜 이렇게 코드가 긴지 모르겠다.

 

이 코드를 구현하는 데 사용한 Rust Feature는 다음과 같다.

 

1. #derive 매크로

 해당 구조체에 Clone, Copy 트레이트를 구현해줄 필요가 있는데 그 트레이트가 자명할 때 사용한다.

#[derive(Clone)]
#[derive(Copy)]
struct Point {
    i: i32,
    j: i32,
}

2. Rust에서의 operator overloading

 Rust에서 정의한 구조체들끼리 연산을 정의하고 싶다면 std::ops::Add 트레이트를 구현한다. 당연히 operator+ 말고도 많은 operator를 구현할 수 있다. 각각의 operator들을 오버로딩하려면 그에 대응되는 trait를 찾아서 구현해야 한다. 몇몇 자명한 trait는 #derive로 처리해줄 수 있다. 자세한 사항은 공식문서를 보면 된다. https://doc.rust-lang.org/std/ops/index.html

impl Add for Point {
    type Output = Point;

    fn add(self, other: Point) -> Self::Output {
        Point{
            i: self.i + other.i,
            j: self.j + other.j,
        }
    }
}

3. 입력받기

정해진 포맷 같은 걸로 대충 입력받으면 된다. Rust로 PS 하는 사람들은 이 방법이 좀 불편하다 보니 자신만의 IO library를 만들곤 한다.

주의사항으로, String이 random access를 지원하지 않으므로 Vec<String>이 아닌 Vec<Vec<...>>을 사용하여 문제를 해결한다. Vec::from 또는 Vec::from_iter 중 상황에 맞는 것을 사용하면 쉽게 만들 수 있다. 다만 이 방법은 모든 입력이 u8 범위라는 전제 하에서만 사용 가능한 방법이다. PS 같은 특수한 상황에서나 통하지 보통은 잘 통하지 않는다. 

let mut s = String::new();
std::io::stdin().read_line(&mut s).unwrap();
let n: usize = s.trim().parse().unwrap();

let mut grid = Vec::<Vec<u8>>::with_capacity(n as usize);

for _ in 0..n {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    let to_push = Vec::from(s);
    grid.push(to_push);
}

4. 매크로를 통한 벡터 선언법도 알아두자.

let mut visited = vec![vec![0; n]; n];

5. const 키워드는 컴파일 타임 상수를 정의할 수 있다. 함수에 const를 붙이면 컴파일 타임에 실행 가능한 함수를 만들 수 있다. C++에서 constexpr를 즐겨 사용한 사람은 쉽게 파악이 가능한 부분.

const DVS: [Point; 4] = [
    Point::new(0, 1),
    Point::new(0, -1),
    Point::new(1, 0),
    Point::new(-1, 0),
];

6. 이외에도 참조자가 갖고 있는 데이터를 복사해서 새로운 데이터를 만들고 싶다면 to_owned() method, 기본 타입 사이의 형변환은 as keyword 등... 재미있는 문법이 많음.

while !queue.is_empty() {
    let p = queue.front().unwrap().to_owned();
    let n = visited.len() as i32;
    queue.pop_front().unwrap();

    for dv in DVS {
        let next = p + dv;

        if next.i < 0 || next.i >= n || next.j < 0 || next.j >= n {
            continue
        }

        if grid[next.i as usize][next.j as usize] == '0' as u8 {
            continue
        }

        if visited[next.i as usize][next.j as usize] == 0 {
            visited[next.i as usize][next.j as usize] = 1;
            queue.push_back(next);
            ret += 1;
        }
    }
}