백준-2178번/섬의 개수(java)

 

 

 

 

문제 이해

 

N x M 크기의 그래프가 주어지고 N,M좌표까지의 최단 경로의 칸 이동 수를 구하면 되는 문제이다.

 

문제를 풀기 위해 BFS(너비 우선 탐색)을 사용하였다.

 

문제를 풀때 배열에서의 BFS는 처음 구현해보아서 매우 힘들었다..

 

 

문제 풀이

 

변수

static int N, M;
static int[][] arr;
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
static boolean[][] visit;

dx, dy ==> 상하 좌우 이동을 위해 존재

visit ==> 방문 여부

 

 

<BFS 함수>

public static void BFS(int x, int y) {
    Queue<int[]> queue = new LinkedList<>();
    queue.add(new int[]{x, y});

    while (!queue.isEmpty()) {
        int[] point = queue.poll();
        int pointx = point[0];
        int pointy = point[1];

        for (int i = 0; i < 4; i++) {
            int nextX = pointx + dx[i];
            int nextY = pointy + dy[i];

            if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= M) {
                continue;
            }
            if (visit[nextX][nextY] || arr[nextX][nextY] == 0) {
                continue;
            }

            queue.add(new int[]{nextX, nextY});
            arr[nextX][nextY] = arr[pointx][pointy] + 1;
            visit[nextX][nextY] = true;
        }
    }
}

 

이차원 배열에서 BFS를 구현해야 하므로 큐에 배열을 삽입해준다.

 

다음 좌표가 이미 방문했거나, 0이면 방문하지 않는다.

 

pointx, pointy ==> 현재 좌표

nextX, nextY ==> 다음 좌표

 

<전체 코드>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Problem2178 {

    static int N, M;
    static int[][] arr;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static boolean[][] visit;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        arr = new int[N][M];
        visit = new boolean[N][M];

        for (int i = 0; i < N; i++) {
            String s = br.readLine().trim();
            for (int j = 0; j < M; j++) {
                arr[i][j] = s.charAt(j) - '0';
            }
        }
        visit[0][0] = true;
        BFS(0, 0);
        System.out.println(arr[N - 1][M - 1]);
    }

    public static void BFS(int x, int y) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{x, y});

        while (!queue.isEmpty()) {
            int[] point = queue.poll();
            int pointx = point[0];
            int pointy = point[1];

            for (int i = 0; i < 4; i++) {
                int nextX = pointx + dx[i];
                int nextY = pointy + dy[i];

                if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= M) {
                    continue;
                }
                if (visit[nextX][nextY] || arr[nextX][nextY] == 0) {
                    continue;
                }

                queue.add(new int[]{nextX, nextY});
                arr[nextX][nextY] = arr[pointx][pointy] + 1;
                visit[nextX][nextY] = true;
            }
        }
    }
}