[문제 링크](https://www.acmicpc.net/problem/7562)
성능 요약
메모리: 114744 KB, 시간: 380 ms
분류
너비 우선 탐색, 그래프 이론, 그래프 탐색
제출 일자
2024년 6월 10일 16:22:02
문제 설명
체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?
입력
입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.
각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.
출력
각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다.
예제 입력 1
3
8
0 0
7 0
100
0 0
30 50
10
1 1
1 1
예제 출력 1
5
28
0
설명
나이트의 이동
문제를 해결 하기 위해 BFS 알고리즘을 사용하여 체스판에서 나이트가 이동할 수 있는 최소 횟수를 계산합니다.
코드
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 I;
static int x1, x2, y1, y2;
static int[][] arr;
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 Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st;
int T = Integer.parseInt(br.readLine());
for (int i = 1; i <= T; i++) {
I = Integer.parseInt(br.readLine());
arr = new int[I][I];
visited = new boolean[I][I];
st = new StringTokenizer(br.readLine());
x1 = Integer.parseInt(st.nextToken());
y1 = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
x2 = Integer.parseInt(st.nextToken());
y2 = Integer.parseInt(st.nextToken());
bfs();
sb.append(arr[x2][y2]).append("\n");
}
System.out.println(sb);
}
public static void bfs() {
Queue<int[]> q = new LinkedList<>();
q.add(new int[]{x1, y1});
visited[x1][y1] = true;
while (!q.isEmpty()) {
int[] now = q.poll();
int nx = now[0];
int ny = now[1];
for (int i = 0; i < 8; i++) {
int ox = nx + dx[i];
int oy = ny + dy[i];
if (ox >= 0 && oy >= 0 && ox < I && oy < I) {
if (!visited[ox][oy]) {
q.add(new int[]{ox, oy});
arr[ox][oy] = arr[nx][ny] + 1;
visited[ox][oy] = true;
}
}
}
}
}
}
세부 설명
변수 및 상수 정의
public class Main {
static int I; // 체스판의 크기
static int x1, x2, y1, y2; // 시작 위치(x1, y1)와 목표 위치(x2, y2)
static int[][] arr; // 이동 횟수를 저장하는 배열
static boolean[][] visited; // 방문 여부를 저장하는 배열
static int[] dx = {1, 2, 2, 1, -1, -2, -2, -1}; // 나이트의 이동 방향 (x 좌표 변화량)
static int[] dy = {2, 1, -1, -2, -2, -1, 1, 2}; // 나이트의 이동 방향 (y 좌표 변화량)
- I는 체스판의 크기입니다.
- x1, y1는 나이트의 시작 위치, x2, y2는 목표 위치입니다.
- arr는 나이트가 각 칸에 도달하기까지의 이동 횟수를 저장합니다.
- visited는 각 칸의 방문 여부를 저장합니다.
- dx, dy 배열은 나이트가 이동할 수 있는 8가지 방향을 나타냅니다.
메인 메서드
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st;
int T = Integer.parseInt(br.readLine()); // 테스트 케이스의 개수
for (int i = 1; i <= T; i++) {
I = Integer.parseInt(br.readLine()); // 체스판의 크기 입력
arr = new int[I][I];
visited = new boolean[I][I];
st = new StringTokenizer(br.readLine());
x1 = Integer.parseInt(st.nextToken());
y1 = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
x2 = Integer.parseInt(st.nextToken());
y2 = Integer.parseInt(st.nextToken());
bfs(); // BFS 알고리즘 호출
sb.append(arr[x2][y2]).append("\n"); // 목표 위치까지의 이동 횟수를 결과 문자열에 추가
}
System.out.println(sb); // 결과 출력
}
- 테스트 케이스의 개수 T를 입력받습니다.
- 각 테스트 케이스마다 체스판의 크기 I, 시작 위치, 목표 위치를 입력받습니다.
- arr 배열과 visited 배열을 초기화합니다.
- bfs 메서드를 호출하여 시작 위치에서 목표 위치까지의 최소 이동 횟수를 계산합니다.
- 결과를 StringBuilder 객체에 저장하고, 모든 테스트 케이스가 끝난 후 결과를 출력합니다.
BFS 메서드
public static void bfs() {
Queue<int[]> q = new LinkedList<>();
q.add(new int[]{x1, y1});
visited[x1][y1] = true;
while (!q.isEmpty()) {
int[] now = q.poll();
int nx = now[0];
int ny = now[1];
for (int i = 0; i < 8; i++) {
int ox = nx + dx[i];
int oy = ny + dy[i];
if (ox >= 0 && oy >= 0 && ox < I && oy < I) {
if (!visited[ox][oy]) {
q.add(new int[]{ox, oy});
arr[ox][oy] = arr[nx][ny] + 1;
visited[ox][oy] = true;
}
}
}
}
}
- Queue를 사용하여 BFS 탐색을 수행합니다.
- q.add(new int[]{x1, y1});를 통해 시작 위치를 큐에 추가하고, 해당 위치를 방문했다고 표시합니다.
- 큐가 빌 때까지 반복하면서 현재 위치를 큐에서 꺼내고, 나이트가 이동할 수 있는 8가지 방향에 대해 새로운 위치를 계산합니다.
- 새로운 위치가 체스판 범위 내에 있고 방문하지 않은 경우, 큐에 추가하고, 이동 횟수를 갱신하며, 방문 여부를 업데이트합니다.
1. 큐에서 현재 위치 꺼내기
int[] now = q.poll();
int nx = now[0]; // 현재 위치 x좌표
int ny = now[1]; // 현재 위치 y좌표
- q.poll()은 큐에서 현재 위치를 꺼냅니다. now 배열에는 현재 나이트의 위치가 [nx, ny] 형태로 저장됩니다.
- nx와 ny는 현재 위치의 x, y 좌표입니다.
2. 8가지 방향으로 이동 탐색
for (int i = 0; i < 8; i++) {
int ox = nx + dx[i];
int oy = ny + dy[i];
- for (int i = 0; i < 8; i++)는 나이트가 이동할 수 있는 8가지 방향을 탐색하기 위해 8번 반복하는 반복문입니다.
- dx와 dy 배열은 나이트가 이동할 수 있는 8가지 방향을 나타냅니다. 각 방향에 대해 이동 후의 새로운 좌표 (ox, oy)를 계산합니다.
나이트는 체스판에서 다음과 같은 8가지 방향으로 이동할 수 있습니다:
하나. (1, 2)
둘. (2, 1)
셋. (2, -1)
넷. (1, -2)
다섯. (-1, -2)
여섯. (-2, -1)
일곱. (-2, 1)
여덟. (-1, 2)
이 방향들을 dx와 dy 배열로 나타내면 다음과 같습니다:
dx = {1, 2, 2, 1, -1, -2, -2, -1}
dy = {2, 1, -1, -2, -2, -1, 1, 2}
이 배열을 사용해 새로운 위치를 계산할 수 있습니다. 예를 들어, dx[0]과 dy[0]은 첫 번째 방향 (1, 2)을 나타냅니다.
3. 새로운 위치가 유효한지 확인
if (ox >= 0 && oy >= 0 && ox < I && oy < I) {
- ox와 oy가 체스판의 범위 내에 있는지 확인합니다. ox와 oy가 모두 0 이상이고, I보다 작은지 확인합니다. 이는 새로운 위치가 체스판 밖으로 나가지 않도록 하기 위함입니다.
4. 새로운 위치가 방문되지 않았는지 확인하고 큐에 추가
if (!visited[ox][oy]) {
q.add(new int[]{ox, oy});
arr[ox][oy] = arr[nx][ny] + 1;
visited[ox][oy] = true;
}
- 새로운 위치가 아직 방문되지 않았는지 확인합니다. 방문하지 않았다면 다음을 수행합니다:
- q.add(new int[]{ox, oy});를 통해 새로운 위치를 큐에 추가합니다.
- arr[ox][oy] = arr[nx][ny] + 1;을 통해 새로운 위치까지의 이동 횟수를 갱신합니다. 현재 위치 arr[nx][ny]에서 한 번 더 이동했으므로 +1을 해줍니다.
- visited[ox][oy] = true;를 통해 새로운 위치를 방문했다고 표시합니다.
BFS 메서드 요약
- for (int i = 0; i < 8; i++): 나이트가 이동할 수 있는 8가지 방향을 모두 탐색하기 위해 사용합니다.
- dx와 dy 배열: 나이트가 이동할 수 있는 8가지 방향을 저장하고 있습니다.
- ox와 oy 계산: 현재 위치에서 각 방향으로 이동한 새로운 위치를 계산합니다.
- 범위 체크및 방문 여부 확인: 새로운 위치가 체스판 범위 내에 있는지 확인하고, 방문하지 않았으면 큐에 추가하고 이동 횟수를 갱신합니다.
BFS 핵심 동작
1. 큐 초기화 및 시작 위치 설정: 나이트의 시작 위치를 큐에 추가하고, 해당 위치를 방문했다고 표시합니다.
2. 반복문을 통한 탐색: 큐가 빌 때까지 반복하여, 현재 위치에서 나이트가 이동할 수 있는 모든 방향으로 이동해 봅니다.
3. 방문 여부 및 이동 횟수 갱신: 새로운 위치가 체스판 범위 내에 있고 아직 방문하지 않은 경우, 해당 위치를 큐에 추가하고, 시작 위치로부터의 이동 횟수를 갱신하고 방문 여부를 표시합니다.
'여러가지 > 알고리즘 & 자료구조' 카테고리의 다른 글
완전탐색 & 시뮬레이션 - 1 (0) | 2024.06.12 |
---|---|
[백준] 신기한 소수 찾기 - 2023번 (1) | 2024.06.10 |
[백준] 열 개씩 끊어 출력하기 - 11721번 (0) | 2024.06.01 |
[백준] KMP는 왜 KMP일까? - 2902번 (0) | 2024.06.01 |
동적 프로그래밍과 반대 개념 프로그래밍 (1) | 2024.05.31 |