[99클럽 코테 스터디] 9일차

오늘의 학습 키워드

• BFS

문제 - 미들러

나이트의 이동

풀이

import java.util.*;

class Main {
  static int testCase;
  static int l;

  static int[][] board;
  static boolean[][] visited;
  static int[] dx = {1, 2, 2, 1, -1, -2, -2, -1};
  static int[] dy = {2, 1, -1, -2, -2, -1, 1, 2};

  static void bfs(int startX, int startY, int targetX, int targetY) {
    Queue<int[]> q = new LinkedList<>();
    q.offer(new int[]{startX, startY});
    visited[startX][startY] = true;

    while (!q.isEmpty()) {
      int[] current = q.poll();
      int curX = current[0];
      int curY = current[1];

      if (curX == targetX && curY == targetY) { // 현재위치와 목표위치가 같다면 함수 종료
        return;
      }

      for (int i = 0; i < 8; i++) {
        int nextX = curX + dx[i];
        int nextY = curY + dy[i];

        // 체스(board)의 범위를 벗어나지 않고, 방문한 적이 없다면, 방문처리 해주고 이전 값보다 값을 1 증가시킵니다.
        if (nextX >= 0 && nextX < l && nextY >= 0 && nextY < l && !visited[nextX][nextY]) {
          q.offer(new int[]{nextX, nextY});
          visited[nextX][nextY] = true;
          board[nextX][nextY] = board[curX][curY] + 1;
        }
      }
    }
  }

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    testCase = sc.nextInt();

    while (testCase != 0) {
      testCase--;
      l = sc.nextInt();

      board = new int[l][l];
      visited = new boolean[l][l];

      int currentX = sc.nextInt();
      int currentY = sc.nextInt();

      int targetX = sc.nextInt();
      int targetY = sc.nextInt();

      bfs(currentX, currentY, targetX, targetY);

      System.out.println(board[targetX][targetY]);
    }
  }
}

• BFS를 응용해서 풀이하면 되는 문제입니다.
• 응용한 부분은 다음과 같습니다.
  • 현재 위치와 목표 위치가 같다면, BFS를 종료하는 조건을 추가
  • 체스의 위치를 벗어나면 탐색하지 않는 조건을 추가