[Baekjoon] 7562_나이트의 이동

Silver I

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

---

<나이트의 이동>

문제 

 

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

 

입력

 

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

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

 

 

출력 

 

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

 

 

문제 풀이

   - my solution (Python)

import sys
from collections import deque

def bfs(l, start, end, depth):
    dx=[-2,-2,-1,-1,2,2,1,1] # 한 번에 이동할 수 있는 칸
    dy=[-1,1,-2,2,-1,1,-2,2]

    queue=deque([start])
    visited=[[0]*l for i in range(l)] # 방문 여부
    visited[start[0]][start[1]]=1

    flag=0

    while queue:
        temp=queue.popleft()
        for i in range(8):
            x=temp[0]+dx[i]
            y=temp[1]+dy[i]
            if x>=0 and x<l and y>=0 and y<l: # 체스판 범위 안이라면
                if visited[x][y]==0:
                    visited[x][y]=1 # 방문
                    depth[x][y]=depth[temp[0]][temp[1]]+1 # 이동 수
                    queue.append([x,y])
                    if x==end[0] and y==end[1]: # 이동하려고 하는 칸에 도착
                        flag=1
                        break
        if flag==1:
            break


if __name__=='__main__':
    t=int(input())

    for i in range(t):
        l=int(sys.stdin.readline().strip())
        x,y=map(int, sys.stdin.readline().split()) # 현재 위치
        a,b=map(int, sys.stdin.readline().split()) # 이동 위치

        depth=[[0]*l for j in range(l)]
        bfs(l, [x,y], [a,b], depth)

        print(depth[a][b])

 

- 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 _7562_나이트의이동 {
	static void bfs(int l, int start[], int end[], int depth[][]) {
		int dx[]= {-2,-2,-1,-1,2,2,1,1}; // 이동할 수 있는 칸
		int dy[]= {-1,1,-2,2,-1,1,-2,2};
		
		int visited[][]=new int[l][l]; // 방문 여부
		visited[start[0]][start[1]]=1;
		
		Queue<int []> queue=new LinkedList<>();
		queue.add(start);
		
		int flag=0;
		
		while(queue.size()!=0) {
			 int temp[]=queue.poll();
			 for(int i=0; i<8; i++) {
				 int x=temp[0]+dx[i];
				 int y=temp[1]+dy[i];
				 if(x>=0 && x<l && y>=0 && y<l) { // 체스판 범위 안이라면
					 if(visited[x][y]==0) {
						 visited[x][y]=1; // 방문
						 queue.add(new int[] {x,y});
						 depth[x][y]=depth[temp[0]][temp[1]]+1;
						 if(x==end[0] && y==end[1]) { // 이동하려고 하는 칸에 도착
							 flag=1;
							 break;
						 }
					 }
				 }
			 }
			 if(flag==1) {
				 break;
			 }
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
		
		int t=Integer.parseInt(bf.readLine()); // 테스트 케이스
		
		for(int i=0; i<t; i++) {
			int l=Integer.parseInt(bf.readLine()); // 체스판의 한 변의 길이
			
			int start[]=new int[2]; // 현재 있는 칸
			String s=bf.readLine();
			start[0]=Integer.parseInt(s.split(" ")[0]);
			start[1]=Integer.parseInt(s.split(" ")[1]);
			
			int end[]=new int[2]; // 나이트가 이동하려고 하는 칸
			s=bf.readLine();
			end[0]=Integer.parseInt(s.split(" ")[0]);
			end[1]=Integer.parseInt(s.split(" ")[1]);
			
			int depth[][]=new int[l][l];
			bfs(l,start,end,depth);
			
			System.out.println(depth[end[0]][end[1]]);
		}
	}
}

 

시작 위치에서 한 번에 이동할 수 있는 칸만큼 움직여 나이트가 이동하려고 하는 칸에 도착하면 이동해야 하는 수를 출력해준다

 

• bfs
  : dx, dy = 한 번에 이동할 수 있는 칸
  : flag = break 조건
  : queue가 빌 때까지 반복 -> 제일 처음 값을 pop -> 이동할 수 있는 칸인지 확인하여 체스판 범위 안이며 아직 방문하지 않았다면 queue에 추가 및 방문 check, 이동할 위치의 depth=현재 위치의 depth+1
  : 이동할 위치가 이동하려는 위치와 같다면 종료
• main
  : t = 테스트 케이스
  : l = 체스판의 한 변의 길이
  : x, y = 현재 위치
  : a, b = 이동하려는 위치
  : depth = 이동 횟수 ( result = depth [a][b] )

 

---

생각🤔

 

문제에서 특별한 예외는 없었다. 딱 주어진 조건을 가지고 그래프 탐색하면 해결 -!

컴파일 에러는... java로 제출해야 하는데 python으로 제출해서 발생...

 

---