250x250
250x250
JinSeopKim
Hello World!
JinSeopKim
전체 방문자
오늘
어제
  • 분류 전체보기 (168)
    • Artificial intelligence (14)
      • DeepDiveToAI (3)
      • Pytorch (3)
      • Etc (8)
    • Back-end (19)
      • Spring (10)
      • JPA (9)
    • Language (24)
      • Python (3)
      • Java (11)
      • Swift (10)
    • Math (4)
      • Linear Algebra (4)
    • CodingTest (79)
      • Algolithm (12)
      • Backjoon (25)
      • Programmers (42)
    • Etc (27)
      • Book Review (3)
      • Adsp (6)
      • Life (2)
      • Docker (1)
      • odds and ends (15)

블로그 메뉴

  • 홈
  • 태그
  • 방명록
  • GitHub

인기 글

태그

  • 카카오
  • 자바
  • SpringMVC
  • certificate
  • 구현
  • Front-end
  • data
  • 코딩테스트
  • 문제풀이
  • DP
  • AI
  • swift
  • 개발자
  • JPA
  • 알고리즘
  • 프로그래머스
  • java
  • BFS
  • ADsP
  • Python
  • 브루트포스
  • uArm
  • ios
  • 선형대수
  • 백준
  • JAVA8
  • 개발
  • 파이썬
  • BOJ
  • 머신러닝

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
JinSeopKim

Hello World!

[BOJ_7562] 나이트의 이동 (Java)
CodingTest/Backjoon

[BOJ_7562] 나이트의 이동 (Java)

2021. 12. 16. 16:41
728x90
728x90

문제링크

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

 

7562번: 나이트의 이동

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수

www.acmicpc.net

문제설명

더보기
더보기
더보기

문제

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

입력

입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.

각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.

출력

각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다.

제한사항

제한시간 메모리제한
1초 256 MB

출처 : https://www.acmicpc.net

문제풀이

👨🏻‍💻 핵심 스킬 👨🏻‍💻
 BFS

나이트의 이동 문제는 BFS를 활용하여 해결 할 수 있습니다. 체스판을 모두 하나의 정점으로 보고, 나이트가 이동할 수 있는 길을 간선으로 연결된 정점들 생각하며 문제를 해결하면 됩니다. 최단거리에 대한 문제이기 때문에 DFS를 사용할 수 없습니다. BFS를 시작 정점부터 돌려주면 이동가능한 모든 보드판의 위치에 최단거리를 기록할 수 있습니다.

이 때 bfs를 돌며 체크된 정점인지 확인을 하기 위하여 정수로 해당 위치의 최단거리를 표시해주면 됩니다.

구현코드

package backjoon_7562;

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

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int testCase = sc.nextInt();

        while ((testCase--) != 0){
            int chessLen = sc.nextInt();
            int[][] board = new int[chessLen][chessLen];
            for(int i = 0; i < chessLen; i++){
                for(int j = 0; j < chessLen; j++){
                    board[i][j] = -1;
                }
            }
            int startX = sc.nextInt();
            int startY = sc.nextInt();
            int finishX = sc.nextInt();
            int finishY = sc.nextInt();

            Queue<Integer> queue = new LinkedList<>();
            queue.add(startX);
            queue.add(startY);
            board[startX][startY] = 0;

            while (!queue.isEmpty()){
                bfs(queue,board);
            }
            System.out.println(board[finishX][finishY]);
        }
    }

    public static void bfs(Queue<Integer> queue, int[][] board){
        int X = queue.remove();
        int Y = queue.remove();
        int[] dX = {-2,-1,1,2,2,1,-1,-2};
        int[] dY = {1,2,2,1,-1,-2,-2,-1};

        for(int i = 0; i < 8; i++){
            if(X + dX[i] >= 0 && X + dX[i] < board.length &&
                    Y + dY[i] >= 0 && Y + dY[i] < board.length){
                if(board[X+dX[i]][Y+dY[i]] == -1) {
                    queue.add(X + dX[i]);
                    queue.add(Y + dY[i]);
                    board[X + dX[i]][Y + dY[i]] = board[X][Y] + 1;
                }
            }
        }
    }
}

 

시간복잡도

테스트 케이스의 수만큼 확인하기 때문에 T를 곱해주어야합니다.

모든 정점에 대하여 한번씩은 수행하기 때문에 V이고 해당 정점과 연결된 8개의 간선을 확인해주기 때문에 E가 됩니다.

따라서 시간 복잡도는 $O(T*(V+E))$가 됩니다.

728x90
728x90
저작자표시 비영리 변경금지

'CodingTest > Backjoon' 카테고리의 다른 글

[BOJ_14226] 이모티콘 (java)  (0) 2021.12.18
[BOJ_14226] 이모티콘 (java)  (0) 2021.12.18
[BOJ_7576] 토마토 (java)  (0) 2021.12.16
[BOJ_2667] 단지번호붙이기 (java)  (0) 2021.12.16
[BOJ_1707] 이분그래프 (java)  (0) 2021.12.15
    'CodingTest/Backjoon' 카테고리의 다른 글
    • [BOJ_14226] 이모티콘 (java)
    • [BOJ_14226] 이모티콘 (java)
    • [BOJ_7576] 토마토 (java)
    • [BOJ_2667] 단지번호붙이기 (java)
    JinSeopKim
    JinSeopKim
    기록📚

    티스토리툴바