[BaekJoon] 백준 7562번 _ 나이트의 이동 for JAVA _ BFS 알고리즘

 

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

7562번: 나이트의 이동

 

 

 

 

문제

 

 

---

 

BFS로 풀었다.

 

 

 

걍 전형적인.. 문제이다.... dx[], dy[]의 범위에만 신경써주면 됨

 

 

 

코드

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


class night{
	int x, y;
	public night(int x, int y){
		this.x = x;
		this.y = y;
	}
	public int getX() {return this.x;}
	public int getY() {return this.y;}
}

public class Baek7562 {
	public static int T, I;
	public static int now[] = new int[2];
	public static int fin[] = new int[2];
	public static int ans[];
	public static int count[][];
	public static int dx[] = {1, 1, -1, -1, 2, 2, -2, -2};
	public static int dy[] = {2, -2, 2, -2, 1, -1, 1, -1};
	public static Queue<night> queue = new LinkedList<night>();
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		T = Integer.parseInt(br.readLine());
		
		ans = new int[T];
		
		for(int i = 0; i < T; i++) {	
			I = Integer.parseInt(br.readLine());
			
			count = new int[I][I];
			
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			now[0] = Integer.parseInt(st.nextToken());
			now[1] = Integer.parseInt(st.nextToken());
			
			st = new StringTokenizer(br.readLine(), " ");
			fin[0] = Integer.parseInt(st.nextToken());
			fin[1] = Integer.parseInt(st.nextToken());
			
			count[now[0]][now[1]] = 1;	
			
			if((now[0] == fin[0]) & (now[1] == fin[1])) ans[i] = 0;
			else {
				
				ans[i] = night_bfs(now[0], now[1]);
			}
			
			queue.clear();
		}
		
		for(int i = 0; i < T; i++)
			System.out.println(ans[i]);
	}
	
	public static int night_bfs(int x, int y) {
		queue.add(new night(x, y));
		
		while(!queue.isEmpty()) {
			night t = queue.remove();
			int tx = t.getX();
			int ty = t.getY();
			
			for(int i = 0; i < 8; i++) {
				int nx = tx + dx[i];
				int ny = ty + dy[i];
				if(nx <= -1 || nx >= I || ny <= -1 || ny >= I) continue;
				
				if((nx == fin[0]) & (ny == fin[1])) return count[tx][ty];
				if(count[nx][ny] == 0) {
					queue.add(new night(nx, ny));
					count[nx][ny] = count[tx][ty] + 1;
				}
			}
		}
		
		return -1;
	}

}

 

 

 

성능

 

 

 

다른 사람 코드를 살펴보면서 안건데

 

now[0] = 어쩌구 일케 말고

 

 

String[] now = br.readLine().split(" ");

 

 

이렇게 하면 되네..~~ㅋ

 

그리고 테스트케이스 돌릴 때 for(int i = 0; i < T 어쩌구 일케 했는데

 

 

while(T-- > 0) 이거 좋은 것 같다.

 

 

 

https://www.acmicpc.net/source/15812393

import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.StringTokenizer;

public class Main {

	
	static int[] dx = {2,1,2,1,-1,-2,-1,-2};
	static int[] dy = {1,2,-1,-2,-2,-1,2,1};
	
	static int[][] map;
	
	static boolean[][] visit;
	
	static int endx;
	static int endy;
	
	static int N, T;
	
	static ArrayDeque<Point> list;
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		T = Integer.parseInt(st.nextToken());
		
		for(int test_case=1;test_case<=T;test_case++) {
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			
			map = new int[N][N];
			visit = new boolean[N][N];
			list = new ArrayDeque<Point>();
			
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			list.add(new Point(x,y));
			visit[x][y] = true;
			
			st = new StringTokenizer(br.readLine());
			endx  = Integer.parseInt(st.nextToken());
			endy  = Integer.parseInt(st.nextToken());
			
			bfs();
		}
	}

	
	public static void bfs() {
		
		while(!list.isEmpty()) {
			Point p = list.remove();
			
			if(p.x ==endx && p.y==endy) {
				System.out.println(map[p.x][p.y]);
				return;
			}
			
			for(int i=0;i<8;i++) {
				int x = p.x + dx[i];
				int y = p.y + dy[i];
				if(x < 0 || y < 0 || x >= N || y >= N)continue;
				if(visit[x][y])continue;
				visit[x][y] = true;
				map[x][y] = map[p.x][p.y]+1;
				list.add(new Point(x,y));
			}
			
		}
	}
}

 

 

이분 코드가 그나마 이해하기 쉬운데

 

 

ArrayDeque를 사용했다.

 

 

찾아보니 Double-Ended Queue라고 해서 큐의 양쪽에서 데이터 삽입 삭제가 가능하다고 한다.

 

 

근데 add랑 remove만 썼던데 왜 저거썼지

 

 

아무튼 bfs() 함수 부분이 효율적인 것 같음

 

 

 

나는 괜히 ans[] 배열 만들었는데..~  이게 더 효율적인 것 같다.