백준 4963 - 섬의 개수

문제

문제 접근 - 대각선 8방향

전형적인 그래프 탐색 문제.

지도에서 육지를 만나면, 출발하여 가로 새로 대각선 으로 연결된 지점은 한 개의 섬으로 보고 탐색하는 과정

입력이 조금 특이해서 애먹었는데

0 0 으로 나오면 끝난다.

즉 계속 돌아가고 있음 (loop)

탐색 전략

지도를 우선 끝까지 순회한다.

  1. 방문 하지 않은 육지(1)을 만나면 섬의 개수를 증가시킨다.
  2. 해당 지점을 기점으로 BFS 진행
  3. 0 과 1 뿐이니 다른 값으로 바꿔 재방문을 막음
  4. 탐색 종료

이런 이유로 인해 딱히 방문 배열을 별도로 만들지는 않았다.

오히려 귀찮아질 것 같은 느낌이 들어서…

구현

입력형태가 귀찮은지라, read_to_string을 통해 한번에 읽어 줄 단위로 파싱했다.

main

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

pub fn solution() -> io::Result<()> {
    let mut input = String::new();
    io::stdin().read_to_string(&mut input)?;

    let mut lines = input.lines();
    let mut results: Vec<isize> = Vec::new();

    loop {
        // w, h 읽기. 입력이 끝났거나 다음 줄이 없으면 break
        let line = match lines.next() {
            Some(l) => l,
            None => break,
        };

        // wh 파싱
        let wh: Vec<isize> = line
            .split_ascii_whitespace()
            .map(|s| s.parse().expect("w h format error"))
            .collect();

        let w = wh[0];
        let h = wh[1];

        // 종료 조건 (0 0)
        if w == 0 && h == 0 {
            break;
        }

        // 맵 데이터 읽기 (h줄)
        let mut map: Vec<Vec<isize>> = Vec::new();

        for _ in 0..h {
            let rows = lines.next().expect(" row error");
            let row: Vec<isize> = rows
                .split_ascii_whitespace()
                .map(|s| s.parse().expect("map data error"))
                .collect();
            map.push(row);
        }

        // 3. 섬의 개수 계산
        let mut island_count = 0;

        for r in 0..h {
            for c in 0..w {
                // 아직 방문하지 않은 육지(1)를 발견하면
                if map[r as usize][c as usize] == 1 {
                    // BFS를 호출해서 연결된 모든 육지를 방문 처리
                    bfs(&mut map, w, h, r, c);
                    island_count += 1;
                }
            }
        }

        results.push(island_count);
    } // loop end

    // 최종 결과 출력
    for count in results {
        println!("{}", count);
    }

    Ok(())
}

BFS

8방향으로 움직여야해서 귀찮았다.

상하좌우대각선…

fn bfs(
    map: &mut Vec<Vec<isize>>,
    w: isize,
    h: isize,
    start_r: isize,
    start_c: isize
) {
    // 8 방향 (상하좌우 및 대각선):
    // dr: [하, 상, 우, 좌, 우하, 좌하, 우상, 좌상]
    let dr: [isize; 8] = [1, -1, 0, 0, 1, 1, -1, -1];
    let dc: [isize; 8] = [0, 0, 1, -1, 1, -1, 1, -1];

    let mut queue = VecDeque::new();

    // 시작점 설정 및 방문 표시
    queue.push_back((start_r, start_c));
    map[start_r as usize][start_c as usize] = 2; // 방문했음을 2로 표시

    while let Some((r, c)) = queue.pop_front() {
        for i in 0..8 {
            let nr = r + dr[i];
            let nc = c + dc[i];

            // 1. 경계 확인
            if nr < 0 || nc < 0 || nr >= h || nc >= w {
                continue;
            }

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

            // 2. 육지(1)이고 아직 방문하지 않은 경우
            if map[nr_usize][nc_usize] == 1 {
                // 방문 표시 (2로 변경)
                map[nr_usize][nc_usize] = 2;
                queue.push_back((nr, nc)); // 다음 탐색 위치 추가
            }
        }
    }
}

최종 코드

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

fn bfs(
    map: &mut Vec<Vec<isize>>,
    w: isize,
    h: isize,
    start_r: isize,
    start_c: isize
) {
    let dr: [isize; 8] = [1, -1, 0, 0, 1, 1, -1, -1];
    let dc: [isize; 8] = [0, 0, 1, -1, 1, -1, 1, -1];

    let mut queue = VecDeque::new();

    queue.push_back((start_r, start_c));
    map[start_r as usize][start_c as usize] = 2;

    while let Some((r, c)) = queue.pop_front() {
        for i in 0..8 {
            let nr = r + dr[i];
            let nc = c + dc[i];

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

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

            if map[nr_usize][nc_usize] == 1 {
                map[nr_usize][nc_usize] = 2;
                queue.push_back((nr, nc));
            }
        }
    }
}

fn main() -> io::Result<()> {
    let mut input = String::new();
    io::stdin().read_to_string(&mut input)?;

    let mut lines = input.lines();
    let mut results: Vec<isize> = Vec::new();

    loop {
        let line = match lines.next() {
            Some(l) => l,
            None => break,
        };

        let wh: Vec<isize> = line
            .split_ascii_whitespace()
            .map(|s| s.parse().expect("w h format error"))
            .collect();

        let w = wh[0];
        let h = wh[1];

        if w == 0 && h == 0 {
            break;
        }

        let mut map: Vec<Vec<isize>> = Vec::new();

        for _ in 0..h {
            let rows = lines.next().expect(" row error");
            let row: Vec<isize> = rows
                .split_ascii_whitespace()
                .map(|s| s.parse().expect(" map error"))
                .collect();
            map.push(row);
        }

        let mut island_count = 0;

        for r in 0..h {
            for c in 0..w {
                if map[r as usize][c as usize] == 1 {
                    bfs(&mut map, w, h, r, c);
                    island_count += 1;
                }
            }
        }

        results.push(island_count);
    }

    for count in results {
        println!("{}", count);
    }

    Ok(())
}

후기

입출력이 BFS 핵심 로직보다 오래 걸린 기이한 문제.

isize -> usize가 살짝 귀찮은데 어떻게 잘 해결했다면 더 좋았을 것 같다.

그래도 난 컴파일러 믿어

잘하자22222