백준 Q7562 - 나이트의 이동

문제 및 입출력

---

풀이

방향벡터를 사용하는 전형적인 유형의 문제이다
수직선 또는 좌표상에서만 사용했던 방향벡터를 나이트의 움직임대로 응용하여 사용하면 된다
초기 변수 세팅과 입출력 설명은 생략하고 bfs 코드만 보자

Queue<int[]> queue = new LinkedList<>();
queue.add(new int[]{curX, curY});
visited[curX][curY] = true;

bfs 순회를 위해 좌표를 담기 위한 큐를 선언하고 처음 시작하는 좌표를 큐에 담아준다
이때 초기 시작값도 방문 체크를 해야하는데, 그 이유는
처음 노드를 방문체크 하지 않으면, 시작점과 목표지점이 동일한 경우 추후 방문시 값을 업데이트하는 오류가 발생하기 때문이다.
ex) (1,1) -> (1,1)

while (!queue.isEmpty()) {
	int[] cur = queue.poll();
	for (int i = 0; i < 8; i++) {
		int nextX = cur[0] + dx[i];
		int nextY = cur[1] + dy[i];

		if (0 <= nextX && nextX < size && 0 <= nextY && nextY < size 
        		&& !visited[nextX][nextY]) {
			queue.add(new int[]{nextX, nextY});
			visited[nextX][nextY] = true;
			map[nextX][nextY] = map[cur[0]][cur[1]] + 1;

			if (nextX == targetX && nextY == targetY) {
				return map[targetX][targetY];
			}
		}
	}
}

총 8가지의 이동루트가 발생하므로 for문을 8번 처리해준다
다음 X,Y 좌표가 적절한 범위에 있고 방문하지 않았으면 탐색을 위해 큐에 담고, 방문처리를 한 후 map[nextX][[nextY] = map[cur[0]][cur[1]] + 1
다음 노드의 값 = 현재 노드의 값 + 1 (횟수 1 증가) 를 해주면 된다

이전에는 따로 count 변수를 선언하여 while문과 for문 사이에 어디에 넣을지 고민을 하였는데, 가독성과 시간단축을 위해 저렇게 한 줄로 적는것이 더 익숙해졌다

현재 노드의 값을 채울때 (map[cur[0]][cur[1]]),
bfs 파라미터 변수가 아님에 주의하자 private static int bfs(int curX, int curY)

---

최종 코드

public class Main {
    static int[] dx = {2, 1, -1, -2, -2, -1, 1, 2};
    static int[] dy = {-1, -2, -2, -1, 1, 2, 2, 1};
    static int[][] map;
    static boolean[][] visited;
    static int targetX, targetY;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        int TC = Integer.parseInt(br.readLine());

        for (int i = 0; i < TC; i++) {
            int size = Integer.parseInt(br.readLine());
            map = new int[size][size];
            visited = new boolean[size][size];

            st = new StringTokenizer(br.readLine());
            int curX = Integer.parseInt(st.nextToken());
            int curY = Integer.parseInt(st.nextToken());

            st = new StringTokenizer(br.readLine());
            targetX = Integer.parseInt(st.nextToken());
            targetY = Integer.parseInt(st.nextToken());

            int result = bfs(curX, curY, size);
            sb.append(result).append("\n");
        }
        System.out.println(sb);
    }

    private static int bfs(int curX, int curY, int size) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{curX, curY});
        visited[curX][curY] = true;

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            for (int i = 0; i < 8; i++) {
                int nextX = cur[0] + dx[i];
                int nextY = cur[1] + dy[i];

                if (0 <= nextX && nextX < size && 0 <= nextY && nextY < size 
                		&& !visited[nextX][nextY]) {
                    queue.add(new int[]{nextX, nextY});
                    visited[nextX][nextY] = true;
                    map[nextX][nextY] = map[cur[0]][cur[1]] + 1;

                    if (nextX == targetX && nextY == targetY) {
                        return map[targetX][targetY];
                    }
                }
            }
        }
        return 0;
    }
}

---

풀이 후기

방향 벡터를 이용하여 푸는 문제는 마스터한 듯 하다
처음에는 익숙지 않아서 처음 소개팅 하는거마냥 뚝딱거렸는데 이제는 뭐 ㅋ
역시 알고리즘 문제를 많이 풀어보고, 문제마다 철저히 유형분석을 하니까 점점 ... 나날히... 나날이... ?