문제

들어가기 전

  • 0 : 길이 없는 빈 공간
  • 1 : 탐색 시작 가능 지점
  • 2 : 이미 탐색한 집

이렇게 처리하기로 생각했다.

접근

  1. 단지를 bfs 로 탐색하고 방문한 부분은 표시한다.
  2. bfs가 끝나면, 탐색 횟수를 반환해 저장해둔다.
  3. 저장해둔 길이를 먼저 출력한다
  4. 이후 정렬된 각 요소를 출력한다.

접근 자체는 쉬웠는데.

정답 코드

use std::{
    collections::VecDeque,
    io::{self, BufWriter, Read, Write},
};

pub fn main() {
    let mut input = String::new();
    io::stdin()
        .read_to_string(&mut input)
        .expect("input expected");

    let mut lines = input.lines();
    let n: usize = lines.next().expect("N expected").trim().parse().unwrap();

    let mut apt_map: Vec<Vec<usize>> = Vec::new();

    for _ in 0..n {
        let line_str = lines.next().expect("apt Line expected");

        let apt_line: Vec<usize> = line_str
            .trim()
            .chars()
            .filter_map(|c| c.to_digit(10))
            .map(|d| d as usize)
            .collect();
        apt_map.push(apt_line);
    }

    let mut complexes: Vec<usize> = Vec::new();

    // bfs 호출
    for r in 0..n {
        for c in 0..n {
            if apt_map[r][c] == 1 {
                let complex_len = bfs(&mut apt_map, r as isize, c as isize, n as isize);
                complexes.push(complex_len);
            }
        }
    }

    complexes.sort();

    let mut ans_buf = BufWriter::new(io::stdout().lock());
    let len_ans = complexes.len();
    writeln!(ans_buf, "{}", len_ans).expect("write failed");
    for i in 0..len_ans {
        writeln!(ans_buf, "{}", complexes[i]).expect("complex line write failed");
    }
    ans_buf.flush().expect("flush failed");
}

fn bfs(apt_map: &mut Vec<Vec<usize>>, start_r: isize, start_c: isize, n: isize) -> usize {
    let mut complex_len = 0;

    let mut queue: VecDeque<(isize, isize)> = VecDeque::new();
    const DR: [isize; 4] = [1, -1, 0, 0];
    const DC: [isize; 4] = [0, 0, -1, 1];

    complex_len += 1;
    queue.push_back((start_r, start_c));

    apt_map[start_r as usize][start_c as usize] = 2;

    while let Some((r, c)) = queue.pop_front() {
        for i in 0..4 {
            let nr = r + DR[i];
            let nc = c + DC[i];

            if nr < 0 || nr >= n || nc < 0 || nc >= n {
                continue;
            }

            let nr_usize = nr as usize;
            let nc_usize = nc as usize;

            if apt_map[nr_usize][nc_usize] == 1 {
                complex_len += 1;

                apt_map[nr_usize][nc_usize] = 2;
                queue.push_back((nr, nc));
            }
        }
    }

    complex_len
}

마무리

IO 쪽이랑, 갱신 로직을 한 번 누락하는 바람에 많이 틀렸던 문제

차근차근 개선해나가야 했던 문제!

사실 uszie 와 isize 를 오가는 것도 귀찮은데…

좋은 방법 없을까..?

trim()은 소중하다. 잘 기억하자.

  • 배열 인덱스 : usize
  • 좌표 계산 : (음수 가능성) -> isize

캐스팅하여 사용하자.