[알고리즘] 백준 7562 나이트의 이동, 4693 섬의개수 -dfs, bfs- 자바

www.acmicpc.net/problem/7562

7562번: 나이트의 이동

 

 

 

 

백준 7562 나이트의 이동을 풀어봤습니다.

 

방향만 잘 설정해주면됩니다.

평소 map크기를 size+2 해서 index out of error를 해결했는데 여기서는 불편해서 비교문으로 처리를 했는데 이게 더 간편한거같아서 애용하려합니다. 

 

풀이는 다음과 같습니다.

 

[Java]

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    private static int size;
    private static int answer = 0;
    private static boolean[][] isVisited;
    private static int[] dx = {-2, -1, 1, 2, 2, 1, -1, -2};
    private static int[] dy = {1, 2, 2, 1, -1, -2, -2, -1};
    private static int startX;
    private static int startY;
    private static int desX;
    private static int desY;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int testCaseCnt = Integer.parseInt(sc.nextLine());
        for (int i = 0; i < testCaseCnt; i++) {
            size = sc.nextInt();
            isVisited = new boolean[size][size];
            startX = sc.nextInt();
            startY = sc.nextInt();
            desX = sc.nextInt();
            desY = sc.nextInt();
            bfs(new Point(startX, startY, 0));
            System.out.println(answer);
        }

    }

    private static void bfs(Point point) {
        Queue<Point> queue = new LinkedList<>();
        queue.offer(point);
        isVisited[point.x][point.y] = true;
        while (!queue.isEmpty()) {
            Point point2 = queue.poll();
            if (point2.x == desX && point2.y == desY) {
                answer = point2.count;
                break;
            }
            for (int i = 0; i < 8; i++) {
                int x2 = point2.x + dx[i];
                int y2 = point2.y + dy[i];
                int count = point2.count + 1;
                if ((x2 >= 0 && x2 < size && y2 < size && y2 >= 0) && !isVisited[x2][y2]) {
                    queue.offer(new Point(x2, y2, count));
                    isVisited[x2][y2] = true;
                }
            }
        }
    }

    static class Point {
        int x;
        int y;
        int count;

        Point(int x, int y, int count) {
            this.x = x;
            this.y = y;
            this.count = count;
        }
    }
}

 

 

 

[2020-12-26]

이와 비슷한 문제로 섬의 개수라는 문제도 있습니다. 

www.acmicpc.net/problem/4963

4963번: 섬의 개수

원리는 똑같으므로 풀이만 작성해놓겠습니다.

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Main {
    private static int[] dr = {-1, -1, -1, 0, 1, 1, 1, 0};
    private static int[] dc = {-1, 0, 1, 1, 1, 0, -1, -1};
    private static int w; //너비
    private static int h; //높이
    private static int[][] map;
    private static boolean[][] isVisited;
    private static int answer = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        w = sc.nextInt();
        h = sc.nextInt();
        while (w != 0 && h != 0) {
            answer = 0;
            map = new int[h][w];
            isVisited = new boolean[h][w];
            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    map[i][j] = sc.nextInt();
                }
            }
            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    if (!isVisited[i][j] && map[i][j] == 1) {
                        bfs(i, j);
                    }
                }
            }
            System.out.println(answer);
            w = sc.nextInt();
            h = sc.nextInt();
        }
    }

    private static void bfs(int r, int c) {
        Queue<Point> queue = new LinkedList<>();
        queue.offer(new Point(r, c));
        isVisited[r][c] = true;
        while (!queue.isEmpty()) {
            Point point = queue.poll();
            r = point.r;
            c = point.c;
            for (int i = 0; i < 8; i++) {
                int r2 = point.r + dr[i];
                int c2 = point.c + dc[i];
                if (r2 >= 0 && r2 < h && c2 >= 0 && c2 < w && !isVisited[r2][c2] && map[r2][c2] == 1) {
                    isVisited[r2][c2] = true;
                    queue.offer(new Point(r2, c2));
                }
            }
        }
        answer++;
    }

    static class Point {
        int r;
        int c;

        Point(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }
}

 

댓글과 공감은 큰 힘이 됩니다. 감사합니다. !!