mingssssss

1. 문제

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

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 answer;
	static int[][] map;
	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 };

	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 M = Integer.parseInt(st.nextToken());
        
        // M만큼 반복
		for (int k = 0; k < M; k++) {
			
			int result = 0;
			
			int[][] start = new int[1][2];
			int[][] goal = new int[1][2];

			st = new StringTokenizer(br.readLine());
			int N = Integer.parseInt(st.nextToken());
			map = new int[N][N];
			visited = new boolean[N][N];

			st = new StringTokenizer(br.readLine());
			start[0][0] = Integer.parseInt(st.nextToken());
			start[0][1] = Integer.parseInt(st.nextToken());

			st = new StringTokenizer(br.readLine());
            // 도착지점 1로 설정
			map[Integer.parseInt(st.nextToken())][Integer.parseInt(st.nextToken())] = 1;
            // 입력 종료
            
			System.out.println(BFS(start[0][0], start[0][1], map, visited));

		}

	}

	public static int BFS(int r, int c, int[][] map, boolean[][] visited) {

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

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

		answer = 0;
		
		while (!q.isEmpty()) {

			int[] now = q.poll();

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

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

				if (nextX < 0 || nextY < 0 || nextX >= map.length || nextY >= map.length) {
					continue;
				}

				if (visited[nextX][nextY] == true) {
					continue;
				}

				if (map[nextX][nextY] == 1) {
					answer = map[now[0]][now[1]] + 1;
					return answer;
				}


				visited[nextX][nextY] = true;
				map[nextX][nextY] = map[now[0]][now[1]] + 1;
				q.add(new int[] { nextX, nextY });

			}
		}

		return answer;

	}

}

3. 리뷰

시작지점과 종료지점이 주어지고, 나이트의 이동 범위가 주어졌을 때,

시작지점에서 종료지점까지의 이동의 최솟값을 구하는 문제이다.

이것 역시 전형적인 bfs 문제였는데, 이동 횟수를 어떻게 설정해야 하는지

처음에 생각을 못 해서 고민했었다.

체스판에 이동할 수 있다면 현재 지점에서 +1을 하여서 전체 체스판에

이동거리를 표시했다. bfs는 최단거리 이동을 보장하므로,

해당 좌푯값이 1이라면 현재 좌푯값에서 1만 더하면 최소거리가 나온다.

배열에 모든 정보가 있으므로, 배열을 바꿀 필요가 없다면 배열을 직접 수정하고,

배열을 수정하지 못 하는 경우는 체크하는 배열을 따로 만들어서 이동거리값을 표시하면 된다.

다양한 문제를 풀어서 여러가지 유형을 익히는 것이 중요하다고 생각했다.