백준 18404 현명한 나이트

hyeon·2022년 5월 13일
0

알고리즘 연습

목록 보기
11/23

문제 : 현명한 나이트

문제링크
실버 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;
					}
				}
			}
		}
	
	}
}
profile
남기고 싶은 개발자입니다 :>

0개의 댓글