백준 7562번 : 나이트의 이동
이번 문제는 총 n번의 테스트 케이스 중 l*l 만큼 크기의 체스판에서 현재 나이트가 있는 칸, 나이트가 이동하려는 칸이 각각 주어진다.
n번 동안 체스판 한 변의 길이 l과 시작점 x,y 좌표, 도착점 x,y 좌표가 주어지고 시작점에서 도착점까지 도달하는데에 걸리는 횟수를 리턴하는 문제이다.
사실 이 문제는 좌표 문제니까 2차원 배열을 활용하여 푸는 문제이고,
dx, dy 이동 방향만 잡아줄 수 있다면 풀 수 있다.
다만, 이동 방향이 나이트의 이동 방식을 생각해야하고,
각 실행, 종료 조건에 대해 조금 생각해야하기 때문에 까다로울 수 있다.
가장 먼저 나이트의 이동 방향은 아래와 같다.
1
2
3
4
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};
...
각 방향에 대한 설명은 다음과 같다.
1
2
3
4
5
6
7
8
dx[0] = -2, dy[0] = 1: 현재 위치에서 왼쪽으로 2칸, 위로 1칸 이동
dx[1] = -1, dy[1] = 2: 현재 위치에서 왼쪽으로 1칸, 위로 2칸 이동
dx[2] = 1, dy[2] = 2: 현재 위치에서 오른쪽으로 1칸, 위로 2칸 이동
dx[3] = 2, dy[3] = 1: 현재 위치에서 오른쪽으로 2칸, 위로 1칸 이동
dx[4] = 2, dy[4] = -1: 현재 위치에서 오른쪽으로 2칸, 아래로 1칸 이동
dx[5] = 1, dy[5] = -2: 현재 위치에서 오른쪽으로 1칸, 아래로 2칸 이동
dx[6] = -1, dy[6] = -2: 현재 위치에서 왼쪽으로 1칸, 아래로 2칸 이동
dx[7] = -2, dy[7] = -1: 현재 위치에서 왼쪽으로 2칸, 아래로 1칸 이동
나이트는 L 자 방향으로 이동할 수 있으며 이 이동경로를 dx, dy로 표현한 것이다.
다음은 dx, dy와 같이 전역 변수로 선언된 변수들이다.
1
2
3
4
5
6
public class Main {
static boolean[][] visited;
static int[][] arr;
static int[] start, end;
static int l;
...
각각 visited 는 방문 여부 체크, arr은 체스판, start와 end는 입력 받는 각 시작점, 도착점 좌표이다.
마지막으로 l은 체스판 한 변의 길이이다.
로직에서 공통으로 사용될 변수들을 선언했으니 메인 로직으로 들어가 데이터 가공을 할 차례이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public static void main(String[] args) throws java.io.IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
StringTokenizer st;
while (n-- > 0) {
l = Integer.parseInt(br.readLine());
arr = new int[l][l];
visited = new boolean[l][l];
for (int i = 0; i < 2; i++) {
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
if (i == 0) {
start = new int[]{x, y};
} else {
end = new int[]{x, y};
}
}
if (start[0] == end[0] && start[1] == end[1]) {
System.out.println(0);
continue;
}
bfs();
}
}
메인 함수는 언제나와 같이 받아오는 데이터들을 가공하여 활용해야한다.
기본적인 것들은 제외하고 while문 내부의 상황을 순서대로 볼 것이다.
while문
- 총 n번의 테스트 케이스를 받아올 것이기 때문에 n 번 만큼 while문을 반복시킨다.
- 다음으로는 체스판인 arr 배열을 각 테스트 케이스마다 초기화 해준다. 물론, l 크기의 정사각형이다.
- 마찬가지로 원활한 탐색을 위해 방문 여부를 체크해야하기 때문에 visited 배열도 l 크기 만큼 초기화한다.
- 여기까지 되었다면 다음은 start와 end 좌표를 한 번씩 입력받아야 한다. 고정적으로 두 번이기 때문에 반복문을 2회 실행시킨다.
- 이때 StringTokenizer를 활용해 x와 y를 입력 받고 반복문 실행 중 처음 입력된 x,y 좌표는 시작좌표, 다음으로 입력된 x,y 좌표는 도착좌표이기 때문에 조건문으로 나누어 각각의 일차원 배열 타입 변수에 할당해주었다.
- 이제 입력되는 데이터에 대한 가공처리는 끝났다. 최단거리로 도착좌표까지의 횟수를 리턴해야한다.
- 단, 시작점과 도착점이 같은 경우에는 이동한 횟수가 없기 때문에 0을 리턴해야한다. 그래서 bfs 탐색 전 조건문을 활용해 이 엣지케이스를 걸러주고 다음 테스트 케이스로 넘어가기 위해 continue를 활용, while 반복문을 다시 실행한다.
- 7번에 해당하지 않는다면 최단거리 탐색을 진행해야한다. 이제 bfs가 실행된다.
main 로직이 복잡해 보일 수 있기 때문에 최대한 자세히 작성했다.
순서대로 읽어본다면 어려움없이 로직 흐름에 대해 알 수 있을 것이다.
이제 8번까지 도달한 테스트 케이스들은 bfs, 너비 우선 탐색을 진행해야한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
...
public static void bfs() {
Queue<int[]> q = new LinkedList<>();
q.offer(start);
visited[start[0]][start[1]] = true;
while(!q.isEmpty()) {
int[] cur = q.poll();
if (cur[0] == end[0] && cur[1] == end[1]) {
System.out.println(arr[end[0]][end[1]]);
return;
}
for (int i = 0; i < 8; i++) {
int nx = cur[0] + dx[i];
int ny = cur[1] + dy[i];
if (nx >= 0 && ny >= 0 && nx < l && ny < l) {
if (!visited[nx][ny]) {
q.offer(new int[]{nx, ny});
visited[nx][ny] = true;
arr[nx][ny] = arr[cur[0]][cur[1]] + 1;
}
}
}
}
}
}
사실 bfs 탐색에 대한 함수를 따로 구현하지 않고 main 함수 내에 작성해도 되지만 가독성이 떨어질 수 있고, 내가 작성하다가도 헷갈려서 무조건 길어진다 싶으면 함수로 빼는 경우가 많다.
여튼, 이제 bfs를 실행해야하는데, 사실 횟수를 중첩해서 다음 좌표로 이동하는 bfs 탐색이라 이전에 풀었던 것들과 다를 건 없다.
다만, while문 내에서 볼 수 있듯이 if 조건으로 도달한 위치가 end 좌표와 같으면 end 좌표의 값을 출력하고 void 리턴하게끔 되어있는데, 이건 main 함수에서 반복문이 실행되면서 각각의 테스트 케이스 마다 이동횟수를 리턴해야하기 때문에 이렇게 구현했다.
이 방법 말고도 별개의 변수에 담아서 리턴하거나 해도 되긴하는데, 굳이 싶어서 함수 종료와 값 출력을 동시에 했다.
이외의 bfs 로직은 순서대로 아래와 같다.
- bfs 탐색을 위해 큐를 선언, 초기화한다.
- 큐에 main에서 입력 받은 시작 좌표를 삽입한다.
- 마찬가지로 visited 배열의 해당 위치에 대한 방문 여부를 true로 변경한다.
- 큐가 빌때까지 반복문을 실행한다.
- cur에 현재 위치를 담는다.
- if 조건으로 현재위치와 도착위치가 같은지 체크하고 같다면 현재(도착)위치의 값을 출력하고 함수를 종료한다. 같지 않다면 7번을 진행한다.
- 반복문을 실행시켜 8방향 탐색을 진행한다. 나이트는 L자 형태로 최대 8방향으로 이동할 수 있다. 이를 위해 dx와 dy 배열에 각 방향을 담아주었다.
- nx와 ny에 현재좌표 + 방향으로 도달한 위치를 각각 저장한다.
- 조건으로 체스판을 벗어나지 않는지 확인한다. 벗어나면 유효한 방향이 아니다. 다시 반복문을 실행시켜 유효한 방향을 찾는다.
- 유효한 방향이고 방문하지 않았다면 큐에 도달한 위치를 삽입하고 이 위치에 대한 방문 여부를 true로, 이전 좌표까지의 값에 1을 더 한다.
이와 같은 로직이 반복되면 최종 도달한 목적지에는 최단 거리로 탐색 후 이동한 횟수가 저장된다.
이러한 방식으로 각 테스트 케이스의 이동 횟수를 리턴하면 된다.
전체 소스 코드는 다음과 같다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
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 boolean[][] visited;
static int[][] arr;
static int[] start, end;
static int l;
public static void main(String[] args) throws java.io.IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
StringTokenizer st;
while (n-- > 0) {
l = Integer.parseInt(br.readLine());
arr = new int[l][l];
visited = new boolean[l][l];
for (int i = 0; i < 2; i++) {
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
if (i == 0) {
start = new int[]{x, y};
} else {
end = new int[]{x, y};
}
}
if (start[0] == end[0] && start[1] == end[1]) {
System.out.println(0);
continue;
}
bfs();
}
}
public static void bfs() {
Queue<int[]> q = new LinkedList<>();
q.offer(start);
visited[start[0]][start[1]] = true;
while(!q.isEmpty()) {
int[] cur = q.poll();
if (cur[0] == end[0] && cur[1] == end[1]) {
System.out.println(arr[end[0]][end[1]]);
return;
}
for (int i = 0; i < 8; i++) {
int nx = cur[0] + dx[i];
int ny = cur[1] + dy[i];
if (nx >= 0 && ny >= 0 && nx < l && ny < l) {
if (!visited[nx][ny]) {
q.offer(new int[]{nx, ny});
visited[nx][ny] = true;
arr[nx][ny] = arr[cur[0]][cur[1]] + 1;
}
}
}
}
}
}
좌표 탐색 문제에서 응용하여 방향을 직접 파악하고 답을 구해야되는 문제는 아직 어렵다.
상하좌우 좌표만 기억하고 있기 때문에 그런 것 같은데, 이 좌표에 대해 좀 골똘히 생각해서 원리를 파악해야한다고 생각한다.
너무 헷갈린다.