[BOJ] 7562번: 나이트의 이동

문제 링크

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

접근한 방식

전형적인 BFS 문제이다.
일반적으로는 탐색을 동서남북으로 한칸 떨어진 위치로 하게되는데, 이 문제는 나이트의 이동 규칙에 따른 위치로 이동하며 탐색하는 것이라는 점만 주의하면 된다.

코드

C++

#include <iostream>
#include <vector>
#include <deque>

using namespace std;

int testCase;
bool visited[300][300];
int l;
int beginI, beginJ, endI, endJ;
vector<int> result; // 결과값 배열
int cnt;
int di[] = { -1, -2, -2, -1, 1, 2, 1, 2 };
int dj[] = { -2, -1, 1, 2, -2, -1, 2, 1 };

void bfs(int i, int j) {
	visited[i][j] = true;
	deque<pair<int, int>> location1, location2;
	location1.push_back(make_pair(i, j));

	while (!location1.empty()) {
		location2 = location1;
		location1.clear();
		while (!location2.empty()) {
			pair<int, int> temp = location2.front();
			location2.pop_front();
			int tempI = temp.first;
			int tempJ = temp.second;

			for (int k = 0; k < 8; k++) {
				int newI = tempI + di[k];
				int newJ = tempJ + dj[k];
				// 탐색하려는 위치가 범위 밖이라면
				if (newI < 0 || newI >= l || newJ < 0 || newJ >= l)
					continue;
				// 탐색 위치가 나이트가 이동하려고 하는 위치이면
				if (newI == endI && newJ == endJ) {
					cnt++;
					return;
				}
				// 탐색 위치에 한번도 방문하지 않았다면
				if (!visited[newI][newJ]) {
					visited[newI][newJ] = true;
					location1.push_back(make_pair(newI, newJ));
				}
			}
		}
		cnt++;
	}
}

void init() {
	for (int i = 0; i < l; i++)
		for (int j = 0; j < l; j++)
			visited[i][j] = false;
}

int main() {
	cin >> testCase;

	for (int i = 0; i < testCase; i++) {
		scanf("%d", &l);
		scanf("%d %d", &beginI, &beginJ);
		scanf("%d %d", &endI, &endJ);

		if (beginI == endI && beginJ == endJ) {
			result.push_back(0);
			continue;
		}

		bfs(beginI, beginJ);
		result.push_back(cnt);

		cnt = 0;
		init();
	}

	for (int i = 0; i < result.size(); i++)
		printf("%d\n", result[i]);

	return 0;
}

Java

import java.util.*;

public class Main {
    static class pair {
        public int i;
        public int j;
        public int cnt;
        public pair(int i, int j, int cnt) {
            this.i = i;
            this.j = j;
            this.cnt = cnt;
        }
    }

    static int testCase;
    static Scanner sc = new Scanner(System.in);
    static int l;
    static int beginI, beginJ, endI, endJ;
    static boolean[][] visited = new boolean[300][300];
    static int di[] = { -1, -2, -2, -1, 1, 2, 1, 2 };
    static int dj[] = { -2, -1, 1, 2, -2, -1, 2, 1 };
    static int cnt;
    static List<Integer> result = new ArrayList<>();

    public static void main(String[] args) {
        testCase = sc.nextInt();
        for (int i = 0; i < testCase; i++) {
            l = sc.nextInt();
            beginI = sc.nextInt(); beginJ = sc.nextInt();
            endI = sc.nextInt(); endJ = sc.nextInt();
            if (beginI == endI && beginJ == endJ) {
                result.add(0);
                continue;
            }
            bfs(beginI, beginJ);

            cnt = 0;
            init();
        }
        for (Integer r : result)
            System.out.println(r);
    }

    static void bfs(int i, int j) {
        visited[i][j] = true;
        Queue<pair> location = new LinkedList<>();
        location.add(new pair(i, j, 0));
        while (!location.isEmpty()) {
            pair temp = location.poll();
            int tempI = temp.i;
            int tempJ = temp.j;
            for (int k = 0; k < 8; k++) {
                int newI = tempI + di[k];
                int newJ = tempJ + dj[k];
                // 탐색하려는 위치가 범위 밖이라면
                if (newI < 0 || newI >= l || newJ < 0 || newJ >= l)
                    continue;
                // 탐색 위치가 나이트가 이동하려고 하는 위치이면
                if (newI == endI && newJ == endJ) {
                    result.add(temp.cnt + 1);
                    return;
                }
                // 탐색 위치에 한번도 방문하지 않았다면
                if (!visited[newI][newJ]) {
                    visited[newI][newJ] = true;
                    location.add(new pair(newI, newJ, temp.cnt + 1));
                }
            }
        }
        cnt++;
    }

    static void init() {
        for (int i = 0; i < l; i++)
            for (int j = 0; j < l; j++)
                visited[i][j] = false;
    }
}