문제링크
실버 1
그래프 탐색
나이트의 최소 이동 수 구하기
격자 판의 크기 N 상대편 말의 갯수 M
나이트의 위치 X,Y
M줄의 상대편 말위치 A,B
최소 이동 수 입력 순으로 출력
최단 거리를 구하는 문제이므로 bfs를 사용해야한다. (물론 가중치가 1일경우 한정)
bfs가 최단거리를 구할 수 있는 이유
bfs를 통해 visited에 최소 이동횟수를 저장하고
해당 visited 값을 출력해준다.
기존 격자형과 똑같은 문제이지만 탐색해야할 범위가 8개이므로 for문을 8번 돌아주면 된다.
import java.util.*;
class xy{
int x;
int y;
xy(int x,int y){
this.x=x;
this.y=y;
}
}
public class 백준18404 {
static int T,M,N,X,Y,cnt=0;
static Scanner scan =new Scanner(System.in);
static int[] dx= {-2,-2,-1,-1,+1,+1,+2,+2};
static int[] dy= {-1,+1,-2,+2,-2,+2,-1,+1};
static int[][] arr;
static int[][] visited;
static ArrayList<xy> list;
static StringBuilder sb=new StringBuilder();
public static void main(String[] args) {
// 입력
N=scan.nextInt();
M=scan.nextInt();
X=scan.nextInt();
Y=scan.nextInt();
list=new ArrayList<>();
for(int i=0;i<M;i++) {
int a=scan.nextInt();
int b=scan.nextInt();
visited=new int [N+1][N+1];
list.add(new xy(a,b));
}
bfs();
for(int i=0;i<list.size();i++) {
xy xy=list.get(i);
sb.append(visited[xy.x][xy.y]-1+" ");
}
System.out.print(sb);
}
static void bfs() {
Queue<xy> q=new LinkedList<>();
q.offer(new xy(X,Y));
visited[X][Y]=1;
while(!q.isEmpty()) {
xy cur=q.poll();
int x=cur.x;
int y=cur.y;
for(int i=0;i<8;i++) {
int nx=cur.x+dx[i];
int ny=cur.y+dy[i];
if(nx>0&&ny>0&&nx<N+1&&ny<N+1) { //격자를 빠져나가지 않으면
if(visited[nx][ny]==0) { //방문하지 않았고
q.offer(new xy(nx,ny));
visited[nx][ny]=visited[x][y]+1;
}
}
}
}
}
}