문제이해
ㅎㅎㅎㅎㅎㅎ
알고리즘 푸는거 재밌다 내 자신 제법 뿌듯해요
맨날 DFS, BFS풀면서 2차원 배열에서 방향배열 나올때마다 상하좌우말고 다르게 움직이는거 나왔음 좋겠다.. 내가 출제자면 움직이는거 변형해서 낼텐데 왜 늘 상하좌우일까 .. 라는 생각을 하곤 했는데 이번 문제에서 나이트가 움직이는게 변형된 형태로 나와서 즐겁게 품ㅎ
무튼..
이 문제는 나이트가 한번에 이동할 수 있는 칸이 정해져 있는데, 나이트가 현재 위치해 있는 칸, 그리고 이동하려는 칸의 위치가 주어지고, 한번에 이동할 수 있는 방법으로 최소 몇번만에 이동할 수 있는지 구하는 문제입니다.
입력
테스트 케이스의 개수가 주어집니다.
각 테스트 케이스는 세 줄로 이루어져있는데, 첫째줄에는 체스판의 한 변의 길이, 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 입력으로 주어집니다.
출력
각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력합니다.
문제 핵심
방향배열의 변형
탐색 시작 점, 탐색 마지막 점 설정
평면 + 최단거리 + 이동 = 2차원 배열을 이용한 BFS , 최단거리배열로 세자
문제접근
방향배열
체스판을 이용해 나이트를 움직이는데, 특정 점에서 시작해 특정 점으로 이동할때 최소로 움직인 횟수를 묻는 것을 보아 2차원 배열에서의 BFS 문제 라고 생각하고 문제를 풀어주면 됩니다.
이때, 나이트가 한번에 움직일 수 있는 경우는 아래와 같습니다.
가상의 사분면을 그려서 1사분면만 놓고 가능한 움직임을 (dx, dy)로 표현하고, 이를 모든 사분면에 적용시켜 각 이동에 대해 (+/-) 조합을 고려한다면 아래와 같이 8가지 경우가 나옵니다.
(dx,dy)=(1,2)
(dx,dy)=(2,1)
...
(dx,dy)=(-1,-2)
(dx,dy)=(-2,-1)
이를 반영하여 아래와 같이 방향배열을 적어주면 됩니다.
시작점, 끝점 설정
시작점과 탐색 종료하는 점이 주어졌을경우
2차원 배열 탐색 문제는 모든 점을 순회하면서 탐색하거나, 시작점과 끝점을 정해주는 경우가 있습니다.
시작점을 정해준다면, BFS를 호출할때 다음과 같이 시작점을 파라미터값으로 대입해주면 됩니다.
끝점을 정해준다면, 다음과 같이 BFS내부의 if문을 통해 조건을 걸어주면 됩니다.
count by 최단거리배열
아 나는 다 구현해놓고 count를 못센다 그치만 이제 잘 셀거라 상관없음
최단거리 배열을 통해 현재 좌표까지의 최단 이동 횟수를 기록하고, BFS 탐색 중 그 값을 계속 업데이트해 나가는 방식으로 이루어집니다.
탐색할 때마다 그 좌표의 최단거리는 이동 전 좌표의 최단 거리 + 1로 업데이트됩니다. 이는 BFS가 먼저 탐색한 경로가 최단 경로임을 보장하기 때문에 가능합니다.
Main
BFS
code
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main{
static int[][] board;
static boolean[][] visited;
static int[][] count;
static int n;
static int[] dx = {-2,-2,2,2,-1,-1,1,1};
static int[] dy = {-1,1,-1,1,-2,2,-2,2};
static int LX, LY ;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine());
StringTokenizer st;
StringBuilder sb= new StringBuilder();;
for(int T =0 ; T<t ; T++){
n = Integer.parseInt(br.readLine());
board = new int[n][n];
visited = new boolean[n][n];
count = new int[n][n];
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
LX = Integer.parseInt(st.nextToken());
LY = Integer.parseInt(st.nextToken());
sb.append(BFS(a,b)).append("\n");
}
System.out.print(sb);
}
static int BFS(int x, int y){
Queue<int[]> q = new LinkedList<int[]>();
q.add(new int[] {x,y}); // 큐에 점 넣기
visited[x][y] = true; // 방문상태 처리
while(!q.isEmpty()){ // 비어있지 않은 동안에 반복
x = q.peek()[0];
y = q.peek()[1];
q.poll();
if (x == LX && y == LY) {
return count[LX][LY];
}
for(int i=0; i<8; i++){
int mx = x+dx[i];
int my = y+dy[i];
if (mx >= 0 && mx < n && my >= 0 && my < n && !visited[mx][my]) {{
q.add(new int[] {mx,my});
count[mx][my] = count[x][y] + 1;
visited[mx][my] = true;
}
}
}
}
return 0;
}
}
