알고리즘 스터디 - bfs

7562

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

문제

7562

접근

• 나이트가 최소의 이동으로 접근하는 문제
• 나이트가 이동할 수 있는 좌표를 설정하고 해당 좌표를 이용해서 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 {
	private static int testCaseCount;
	private static int boardSize;
	private static boolean[][] visited;
	private static int[] dx = {-1, -2, -1, -2, 1, 2, 1, 2};
	private static int[] dy = {2, 1, -2, -1, 2, 1, -2, -1};


	public static void main(String[] args) throws IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		testCaseCount = Integer.parseInt(reader.readLine());
		for(int i = 0; i < testCaseCount; i++) {
			boardSize = Integer.parseInt(reader.readLine());
			visited = new boolean[boardSize][boardSize];
			// bfs 탐색
			String[] start = reader.readLine().split(" ");
			String[] end = reader.readLine().split(" ");
			int x = Integer.parseInt(start[0]);
			int y = Integer.parseInt(start[1]);
			int ex = Integer.parseInt(end[0]);
			int ey = Integer.parseInt(end[1]);
			System.out.println(bfs(x, y, ex, ey));
		}
	}
	
	public static int bfs(int x, int y, int ex, int ey){
		Queue<Integer[]> queue = new LinkedList<>();
		queue.add(new Integer[]{x, y});
		visited[x][y] = true;
		int count = 0;

		while(!queue.isEmpty()){
			int size = queue.size();
				for(int i = 0; i < size; i++){
				Integer[] cur = queue.poll();
				int curX = cur[0];
				int curY = cur[1];

				if(curX == ex && curY == ey){
					return count;
				}

				for(int k = 0; k < dx.length; k++){
					int newX = curX + dx[k];
					int newY = curY + dy[k];
					if(newX >= 0 && newX < boardSize && newY >= 0 && newY < boardSize && !visited[newX][newY]) {
						visited[newX][newY] = true;
						queue.add(new Integer[]{newX, newY});
					}
				}
			}
			count++;
		}
		return count;
	}
}

시행착오

	if(curX == ex && curY == ey){
					return count;
	}

위 부분에서 return 하지 않고 반복문을 종료해서 count가 제대로 반환되지 못했다.

				for(int k = 0; k < dx.length; k++){
					int newX = curX + dx[k];
					int newY = curY + dy[k];
					if(newX >= 0 && newX < boardSize && newY >= 0 && newY < boardSize && !visited[newX][newY]) {
						visited[newX][newY] = true;
						queue.add(new Integer[]{newX, newY});
					}
				}

해당 부분에서 좌표를 통해 다음 큐에 넣는 로직인데 boardSize - 1로 생각해서 접근하여 잘못된 정답이 나왔다.