[Baekjoon] 16948_데스 나이트

Silver I

문제(출처: https://www.acmicpc.net/problem/16948)

---

<데스 나이트>

문제 

 

게임을 좋아하는 큐브 러버는 체스에서 사용할 새로운 말 "데스 나이트"를 만들었다. 데스 나이트가 있는 곳이 (r, c)라면, (r-2, c-1), (r-2, c+1), (r, c-2), (r, c+2), (r+2, c-1), (r+2, c+1)로 이동할 수 있다.

크기가 N×N인 체스판과 두 칸 (r1, c1), (r2, c2)가 주어진다. 데스 나이트가 (r1, c1)에서 (r2, c2)로 이동하는 최소 이동 횟수를 구해보자. 체스판의 행과 열은 0번부터 시작한다.

데스 나이트는 체스판 밖으로 벗어날 수 없다.

 

 

입력

 

첫째 줄에 체스판의 크기 N(5 ≤ N ≤ 200)이 주어진다. 둘째 줄에 r1, c1, r2, c2가 주어진다.

 

 

출력 

 

첫째 줄에 데스 나이트가 (r1, c1)에서 (r2, c2)로 이동하는 최소 이동 횟수를 출력한다. 이동할 수 없는 경우에는 -1을 출력한다.

 

 

문제 풀이

   - my solution (Python)

import sys
from collections import deque

if __name__=='__main__':
    n=int(input()) # 체스판의 크기
    x1,y1,x2,y2=map(int,sys.stdin.readline().split())

    queue=deque([[x1,y1]])
    dx=[-2,-2,0,0,2,2] # 이동
    dy=[-1,1,-2,2,-1,1]
    visited=[[0] * n for i in range(n)] # 방문 여부
    cnt = [[-1] * n for i in range(n)] # 최소 이동 횟수

    visited[x1][y1]=1
    cnt[x1][y1]=0 # 시작 위치
    flag=0


    while queue:
        temp=queue.popleft()
        for i in range(6):
            x=temp[0]+dx[i]
            y=temp[1]+dy[i]
            if x>=0 and x<n and y>=0 and y<n: # 체스판 범위 안
                if visited[x][y]==0: # 아직 방문 x
                    visited[x][y]=1 # 방문
                    cnt[x][y]=cnt[temp[0]][temp[1]]+1 # 이동 횟수 +1
                    queue.append([x,y])
                if x==x2 and y==y2: # 종료 조건
                    flag=1
                    break
        if flag==1:
            break

    print(cnt[x2][y2])

 

- my solution (JAVA)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class _16948_데스나이트 {

	public static void main(String[] args) throws IOException{
		BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
		
		int n=Integer.parseInt(bf.readLine()); // 체스판의 크기
		int x1=0;
		int y1=0;
		int x2=0;
		int y2=0;
		String s=bf.readLine();
		for(int i=0; i<4; i++) {
			x1=Integer.parseInt(s.split(" ")[0]);
			y1=Integer.parseInt(s.split(" ")[1]);
			x2=Integer.parseInt(s.split(" ")[2]);
			y2=Integer.parseInt(s.split(" ")[3]);
		}
		
		Queue<int []>queue=new LinkedList<>();
		int dx[]= {-2,-2,0,0,2,2}; // 이동
		int dy[]= {-1,1,-2,2,-1,1};
		int visited[][]=new int[n][n]; // 방문 여부
		int cnt[][]=new int[n][n]; // 최소 이동 횟수
		
		queue.add(new int[] {x1,y1});
		visited[x1][y1]=1; 
		int flag=0;
		
		while(queue.size()!=0) {
			int temp[]=queue.poll();
			for(int i=0; i<6; i++) {
				int x=temp[0]+dx[i];
				int y=temp[1]+dy[i];
				if(x>=0 && x<n && y>=0 && y<n) { // 체스판 범위 안
					if(visited[x][y]==0) { // 아직 방문 x
						visited[x][y]=1; // 방문
						cnt[x][y]=cnt[temp[0]][temp[1]]+1; // 이동 횟수 +1
						queue.add(new int[] {x,y});
					}
					if(x==x2 && y==y2) { // 종료 조건
						flag=1;
						break;
					}
				}
			}
			if(flag==1) {
				break;
			}
		}
		if(cnt[x2][y2]==0) {
			System.out.println(-1);
		}else {
			System.out.println(cnt[x2][y2]);
		}
	}
}

 

 

이동할 수 있는 만큼 이동하여 범위 확인 후 체스판 범위 안이라면 이동하여 이동 횟수 +1을 해주면 해결할 수 있었다.

 

• n = 체스판 크기
• x1, y1, x2 , y2 = 시작 위치, 이동하려는 위치
• dx, dy = 한 번에 이동할 수 있는 거리
• visited = 방문 여부  -> 시작 위치 (x1, y1) = 1
• cnt = 이동 횟수 저장 -> 시작 위치 (x1, y1) = 0
• flag = 종료 조건
• queue가 빌 때까지 반복 -> 제일 처음 값을 pop -> 이동하여 체스판 범위 안이며 아직 방문하지 않았다면 방문 check 및 이동 횟수 +1, queue  추가/ 이동할 위치와 이동해야 하는 위치가 같다면 종료
• cnt [x2][y2] 출력

---

생각🤔

 

다른 문제 풀다가.. 어려워서 도망쳐왔다.. 😥

문제 해결해서 너무 다행

 

---