mingssssss

1. 문제

https://www.acmicpc.net/problem/16948

2. 코드

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

public class Main {
    
    // 전역 변수 설정
	static int[][] list;
	static boolean[][] visited;
	static int[] dx = { -2, -2, 0, 0, 2, 2 };
	static int[] dy = { -1, 1, -2, 2, -1, 1 };
	static int answer;

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int N = Integer.parseInt(st.nextToken());
		visited = new boolean[N][N];
		list = new int[N][N];

		st = new StringTokenizer(br.readLine());

		int r1 = Integer.parseInt(st.nextToken());
		int c1 = Integer.parseInt(st.nextToken());
		int r2 = Integer.parseInt(st.nextToken());
		int c2 = Integer.parseInt(st.nextToken());
		// 입력 종료

		System.out.println(bfs(r1, c1, r2, c2, N, list, visited));

//		// 출력
//		for (int i = 0; i < N; i++) {
//			for (int j = 0; j < N; j++) {
//				System.out.printf("%d ", list[i][j]);
//			}
//			System.out.println();
//		}

	}

	public static int bfs(int r, int c, int r2, int c2, int N, int[][] list, boolean[][] visited) {

		Queue<int[]> q = new LinkedList<>();

		q.add(new int[] { r, c });
		list[r][c] = 1;

		answer = -1;
		while (!q.isEmpty()) {
            
            int[] now = q.poll();

            for (int i = 0; i < 6; i++) {

                int nextX = now[0] + dx[i];
                int nextY = now[1] + dy[i];

                if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= N) {
                    continue;
                }

                if (list[nextX][nextY] != 0) {
                    continue;
                }

                if (nextX == r2 && nextY == c2) {
                    return list[now[0]][now[1]];

                }

                list[nextX][nextY] = list[now[0]][now[1]] + 1;
                q.add(new int[] { nextX, nextY });
            }
			
		}
		return answer;

	}

}

3. 리뷰

전형적인 bfs 탐색 문제이다.

bfs마다 유형이 조금씩 다른데, 오랜만에 접한 유형이여서 조금 헤맸다..

방문함수를 쓸 필요도 없고, 데스 나이트의 이동 방향이 6방향인데

습관적으로 계속 4방향으로 돌려서 원하는 값이 안 나와서 고생했다..

최소 거리를 구하는 방식은 이 방식으로 풀면 문제 없을 것 같다.

시작 지점을 큐에 넣고 bfs를 돌렸다.

체스판 안에 있고, 다음 갈 좌푯값이 0이 아닌 경우에

현재 거리에서 +1만큼 해줘서 시작 지점으로부터의 거리를 list에 나타냈다.

만약 다음 갈 좌푯값이 도착지점이라면, 현재 값을 answer에 저장해두고 return했다.

만약 while문을 빠져나왔다면, 데스 나이트가 도달할 수 없는 좌푯값이므로

-1을 리턴했다.

bfs는 다양한 유형을 접하면서 익숙해지는게 중요한 것 같다.