[Java] 백준(실버-1) 7562번 - 나이트의 이동
문제 풀이
이번 문제는 너비 우선 탐색인 BFS를 이용해 풀 수 있다.
아이디어 도출
보통, BFS를 이용하여 상,하,좌,우 4 방향으로 이동하는 문제가 많지만, 이번 문제에서는 이동할 수 있는 구간이 8 방향임을 고려하여 접근해야 한다.
나이트의 이동반경을 체스판 위에서 x,y 좌표로 살펴보자.
| x 좌표 | y 좌표 |
|---|---|
| -2 | -1 |
| -2 | 1 |
| -1 | -2 |
| 1 | 2 |
| 1 | -2 |
| 1 | 2 |
| 2 | -1 |
| 2 | 1 |
위와 같이 8방향으로 BFS 탐색을 진행하면 된다. 이제 문제풀이를 위한 아이디어는 정리해보자.
- 각 테스트케이스마다 체스판의 변의 길이와 체스판 배열, 방문 배열을 초기화한다.
- 나이트의 시작위치와 목표위치를 입력받아 BFS 탐색을 진행하는데, 나이트의 시작위치를 먼저 큐에 삽입하여 탐색한다.
- BFS를 통해 나이트가 이동할 때마다(큐에 새로 삽입될 때마다) 이동횟수를 1씩 증가시킨다.
- 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
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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
import java.io.*;
import java.util.*;
class Main {
// 체스판의 크기 선언
static int N;
// 나이트 이동할 수 있는 8칸
static int[] dx = new int[]{-2, -2, -1, -1, 1, 1, 2, 2};
static int[] dy = new int[]{-1, 1, -2, 2, -2, 2, -1, 1};
// 체스판 입력배열과 방문 배열 선언
static int[][] arr;
static boolean[][] visited;
// 나이트의 시작위치와 종료위치를 담을 배열 선언
static Node[] nodes;
static int result;
public static void main(String[] args) throws IOException {
try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
// 1. 나이트는 총 8방향으로 움직일 수 있다.
// 2. 나이트의 시작위치에서 BFS를 통해 탐색해가며 종료위치가 될 경우 탐색을 종료한다.
// 3. 탐색 종료 후 이동횟수를 출력한다.
int T = Integer.parseInt(br.readLine());
while(T --> 0) {
N = Integer.parseInt(br.readLine());
arr = new int[N][N];
visited = new boolean[N][N];
// 나이트의 시작위치와 목표위치를 담는다.
nodes = new Node[2];
for(int i=0; i<2; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
nodes[i] = new Node(start, end);
}
// 나이트의 총 이동횟수를 담기 위한 초기화
result = 0;
// BFS 함수 호출하여 탐색을 시작한다.
bfs();
bw.write(result+"\n");
}
}
}
public static void bfs() {
// 큐에 시작위치를 담고, 방문 여부를 체크한다.
Queue<Node> q = new LinkedList<>();
q.offer(nodes[0]);
visited[nodes[0].x][nodes[0].y] =true;
// 이동해야할 목표 위치
Node target = nodes[1];
while(!q.isEmpty()) {
Node now = q.poll();
// 현재 위치가 종료 위치가 될 경우 탐색을 종료한다.
if(now.x == target.x && now.y == target.y) {
result = now.cnt;
return;
}
for(int dir=0; dir<8; dir++) {
int i = now.x + dx[dir];
int j = now.y + dy[dir];
if(!isRange(i, j)) {
continue;
}
if(!visited[i][j]) {
visited[i][j] = true;
q.offer(new Node(i, j, now.cnt+1));
}
}
}
}
public static boolean isRange(int x, int y) {
if(0<=x && 0<=y && x<N && y<N) {
return true;
}
return false;
}
}
/**
* Node 클래스는 x,y 좌표와 이동횟수를 가진다.
* x,y좌표만을 받아 Node의 인스턴스를 생성한다.
* x,y좌표 및 cnt(이동횟수)를 받아 위치를 이동하는 Node의 인스턴스를 생성한다.
*/
class Node {
int x;
int y;
int cnt;
Node(int x, int y) {
this.x = x;
this.y = y;
this.cnt = 0;
}
Node(int x, int y, int cnt) {
this.x = x;
this.y = y;
this.cnt = cnt;
}
}
출처
- 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.