[백준] 나이트의 이동 다시 풀어보기 (BFS) - JAVA

이 문제는 BFS로 접근

이유 -> BFS는 시작노드에서, 인접한 노드를 탐색 후, 조건에 맞는 인접한 노드를 기준으로 다른 인접한 노드를 탐색한다.

반면에, DFS는 시작노드에서 자식노드를 탐색 후, 그의 자식노드를 탐색한다.

그렇기 때문에 이 문제에서는 인접한 노드를 이용하여 최단거리를 요구하니, BFS를 사용하는 것이 더 유용하다고 판단 

 

package days01;

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

public class B7562 {
	//X의 이동좌표
	static int[] moveX= {-2,-1,1,2,2,1,-1,-2};
	static int[] moveY= {1,2,2,1,-1,-2,-2,-1};
 	static int N; //한 변의 길이 
 	static int tc; //테스트 케이스 수 
 	static int[][] area; //칸 배열
 	static boolean[][] visited;
 	
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		tc=sc.nextInt();
		for (int i = 0; i < tc; i++) {
			N=sc.nextInt();
			area=new int[N][N];
			visited=new boolean[N][N];
			//현재 좌표
			int cx=sc.nextInt();
			int cy=sc.nextInt();
			Point cp=new Point(cx,cy);
			
			//목표 좌표 
			int tx=sc.nextInt();
			int ty=sc.nextInt();
			Point tp=new Point(tx,ty);
			
		System.out.println(	bfs(cp,tp,area, visited));
		}
		

	}

	private static int bfs(Point cp, Point tp, int[][] area, boolean[][] visited) {
		visited[cp.x][cp.y]=true;
		Queue<Point> que=new LinkedList<Point>();
		que.add(cp);
		int nx = 0, ny=0;
		while(!que.isEmpty()) {
			Point p=que.poll();
			if(p.x==tp.x && p.y==tp.y) {
				return area[p.x][p.y];
			}
			for (int i = 0; i <8; i++) {
				nx=p.x+moveX[i];
				 ny=p.y+moveY[i];
				
				if(nx>=0 && nx<area.length && ny>=0 && ny<area.length) {
					
					if(!visited[nx][ny]) {
						area[nx][ny]=area[p.x][p.y]+1;
						que.add(new Point(nx,ny));
						visited[nx][ny]=true;
					
					}
				}
			
			}//for
		}//while
		return -1;
		
	}

}

 

visited - boolean 배열 사용하지 않고 풀기

area 배열을 선언하는 동시에 전체 0으로 초기화가 되고 

방문했던 배열은  값을 가지고 있기 때문에 , 이를 이용함

40초 정도 줄어들었다.

package days01;

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

public class B7562 {
	//X의 이동좌표
	static int[] moveX= {-2,-1,1,2,2,1,-1,-2};
	static int[] moveY= {1,2,2,1,-1,-2,-2,-1};
 	static int N; //한 변의 길이 
 	static int tc; //테스트 케이스 수 
 	static int[][] area; //칸 배열
 	
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		tc=sc.nextInt();
		for (int i = 0; i < tc; i++) {
			N=sc.nextInt();
			area=new int[N][N];
			
			//현재 좌표
			int cx=sc.nextInt();
			int cy=sc.nextInt();
			Point cp=new Point(cx,cy);
			
			//목표 좌표 
			int tx=sc.nextInt();
			int ty=sc.nextInt();
			Point tp=new Point(tx,ty);
			
		System.out.println(	bfs(cp,tp,area));
		}
		

	}

	private static int bfs(Point cp, Point tp, int[][] area) {
	
		Queue<Point> que=new LinkedList<Point>();
		que.add(cp);
		int nx = 0, ny=0;
		while(!que.isEmpty()) {
			Point p=que.poll();
			if(p.x==tp.x && p.y==tp.y) {
				return area[p.x][p.y];
			}
			for (int i = 0; i <8; i++) {
				nx=p.x+moveX[i];
				 ny=p.y+moveY[i];
				
				if(nx>=0 && nx<area.length && ny>=0 && ny<area.length&&area[nx][ny]==0) {
					
				
						area[nx][ny]=area[p.x][p.y]+1;
						que.add(new Point(nx,ny));
					

				}
			
			}//for
		}//while
		return -1;
		
	}

}

 

 

BufferedReader , BufferedWriter , StringTokenizer 이용하기

주요 Method

메서드명	기능
BufferedReader(Reader rd)	rd에 연결되는 문자입력 버퍼스트림 생성
BufferedWriter(Writer wt)	wt에 연결되는 문자출력 버퍼스트림 생성​
int read()	스트림으로부터 한 문자를 읽어서 int 형으로 리턴
int read(char[] buf)	문자배열 buf의 크기만큼 문자를 읽어들임.  읽어들인 문자 수를 리턴
int read(char[] buf, int offset, int length)	buf의 offset위치에서부터 length 길이만큼 문자를 스트림으로부터 읽어들임​
String readLine()	스트림으로부터 한 줄을 읽어 문자열로 리턴​​
void mark()	현재우치를 마킹, 차 후 reset() 을 이용하여 마킹위치부터 시작함
void reset()	마킹이 있으면 그 위치에서부터 다시시각, 그렇지 않으면 처음부터 다시시작
long skip(int n)	n 개의 문자를 건너 뜀
void close()	스트림 닫음
void write(int c)	int 형으로 문자 데이터를 출력문자스트림으로 출력
void write(String s, int offset, int length)	문자열 s를 offset 위치부터 length 길이만큼을 출력스트림으로 출력
void write(char[] buf, int offset, int length)	문자배열 buf의 offset 위치부터 length 길이만큼을 출력스트림으로 출력​​​
void newLine()	줄바꿈 문자열 출력
void flush()	남아있는 데이터를 모두 출력시킴.

 

시간이 되게 많이 줄어들었다.

package days01;

import java.awt.Point;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.StringTokenizer;

public class B7562 {
	//X의 이동좌표
	static int[] moveX= {-2,-1,1,2,2,1,-1,-2};
	static int[] moveY= {1,2,2,1,-1,-2,-2,-1};
 	static int N; //한 변의 길이 
 	static int tc; //테스트 케이스 수 
 	static int[][] area; //칸 배열
 	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		
		tc=Integer.parseInt(br.readLine());
		
		for (int i = 0; i < tc; i++) {
			N=Integer.parseInt(br.readLine());
			area=new int[N][N];
			st=new StringTokenizer(br.readLine(), " ");
			//현재 좌표
			int cx=Integer.parseInt(st.nextToken());
			int cy=Integer.parseInt(st.nextToken());
			Point cp=new Point(cx,cy);
			
			st=new StringTokenizer(br.readLine()," ");
			//목표 좌표 
			int tx=Integer.parseInt(st.nextToken());
			int ty=Integer.parseInt(st.nextToken());
			Point tp=new Point(tx,ty);
			
		System.out.println(	bfs(cp,tp,area));
		}
		
		bw.close();
		br.close();
	}

	private static int bfs(Point cp, Point tp, int[][] area) {
	
		Queue<Point> que=new LinkedList<Point>();
		que.add(cp);
		int nx = 0, ny=0;
		while(!que.isEmpty()) {
			Point p=que.poll();
			if(p.x==tp.x && p.y==tp.y) {
				return area[p.x][p.y];
			}
			for (int i = 0; i <8; i++) {
				nx=p.x+moveX[i];
				 ny=p.y+moveY[i];
				
				if(nx>=0 && nx<area.length && ny>=0 && ny<area.length&&area[nx][ny]==0) {
					
				
						area[nx][ny]=area[p.x][p.y]+1;
						que.add(new Point(nx,ny));
					

				}
			
			}//for
		}//while
		return -1;
		
	}

}