-
[java] 백준 7562 : 나이트의 이동알고리즘 2023. 7. 2. 21:04
https://www.acmicpc.net/problem/7562
package main; import java.io.*; import java.util.*; class Point{ int x,y,cnt; Point(int x, int y, int cnt){ this.x = x; this.y =y; this.cnt = cnt; } } public class Main { static int[] dx = {1,2,2,1,-1,-2,-2,-1}; static int[] dy = {2,1,-1,-2,-2,-1,1,2}; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; int t = Integer.parseInt(br.readLine()); for(int i=1; i<=t; i++) { int I = Integer.parseInt(br.readLine()); st = new StringTokenizer(br.readLine()); int x1 = Integer.parseInt(st.nextToken()); int y1 = Integer.parseInt(st.nextToken()); st = new StringTokenizer(br.readLine()); int x2 = Integer.parseInt(st.nextToken()); int y2 = Integer.parseInt(st.nextToken()); BFS(I, new Point(x1,y1,0), new int[] {x2,y2}); } } public static void BFS(int I, Point start, int[] end) { boolean[][] visited = new boolean[I][I]; Queue<Point> q = new LinkedList<>(); q.add(start); visited[start.x][start.y] = true; while(!q.isEmpty()) { Point now = q.poll(); if(now.x == end[0] && now.y ==end[1]) { System.out.println(now.cnt); return; } for(int i=0; i<8; i++) { int nx = now.x + dx[i]; int ny = now.y + dy[i]; if(0<= nx && nx<I && 0<= ny && ny<I && !visited[nx][ny]) { q.add(new Point(nx,ny,now.cnt+1)); visited[nx][ny]=true; } } } } }
'알고리즘' 카테고리의 다른 글
[java] 프로그래머스 더 맵게 (0) 2023.07.05 [java] 백준 숨바꼭질3 (0) 2023.07.05 <문자열> 프로그래머스 신규 아이디 추천 java (0) 2023.06.18 <문자열> 프로그래머스 문자열 내 마음대로 정렬하기 java (0) 2023.06.18 [java] 백준 좌표정렬하기2 (0) 2023.06.09