알고리즘 스터디-bfs

16948

• 알고리즘 : BFS
• 난이도 : 실버1

문제

16948

접근

• 나이트가 이동할 수 있는 위치를 확인한다.
• 최종 목표에 이동하는 여부를 확인한다.
• 최단 거리로 이동하는 것이다.
  • BFS로 푼다.

풀어보기

package org.example;

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

public class Main {
	static int[] dx = {-2,-2,0,0,2,2};
	static int[] dy = {-1,1,-2,2,-1,1};
	static int N;
	static boolean[][] visited;
	static int moveCount =-1;
	static boolean arrive;

	public static void main(String[] args) throws IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(reader.readLine());
		visited = new boolean[N][N];

		String[] line = reader.readLine().split(" ");
		int r1 = Integer.parseInt(line[0]);
		int c1 = Integer.parseInt(line[1]);
		int r2 = Integer.parseInt(line[2]);
		int c2 = Integer.parseInt(line[3]);

		System.out.println(bfs(r1, c1, r2, c2));
	}

	static int bfs(int r1, int c1, int r2, int c2) {
		Queue<Integer[]> queue = new LinkedList<>();
		queue.offer(new Integer[]{r1,c1});
		visited[r1][c1] = true;

		int moveCount = 0;

		while (!queue.isEmpty() && !arrive) {
			int size = queue.size();
			for(int i = 0; i < size; i++) {
				Integer[] current = queue.poll();
				int cr = current[0];
				int cc = current[1];

				if(cr == r2 && cc == c2) {
					return moveCount;
				}
				for(int j = 0; j < 6; j++){
					int nr = cr + dx[j];
					int nc = cc + dy[j];

					if(nr >= 0 && nr < N && nc >= 0 && nc < N && !visited[nr][nc]){
						visited[nr][nc] = true;
						queue.offer(new Integer[]{nr,nc});
					}
				}
			}
			moveCount++;
		}
		return -1;
	}

}

시행착오

• moveCount의 위치가 방문 할 때마다 증가하게 작성하여 방문한 모든 위치를 확인하였다.
  • 방문한 모든 위치 ->목표를 향해 이동한 횟수 -> 다음 depth에서 증가한다. while문 에서 증가