[백준 7562번/JAVA] 나이트의 이동 (문제 풀이, 코드)

나이트의 이동

[문제]

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

[풀이]

전형적인 그래프 탐색 알고리즘을 이용하는 것이다.

단, 너비우선탐색(bfs)를 써야한다.  최소 횟수니까 bfs는 먼저 도착한 놈이 최소 횟수를 만족한다.

 

[내 코드 알고리즘]

Queue를 만들어서 현재 위치를 넣는다.

Queue에서 item 하나를 꺼내온다. 해당 item이 갈 수 있는 위치를 큐에 다 넣는다.큐가 빌 때 까지 반복하고, Queue에서 꺼낸 item이 목표 위치면 그만한다.

 

[코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class xy {
	int x;
	int y;
	int cnt;

	xy(int x, int y, int cnt) {
		this.x = x;
		this.y = y;
		this.cnt = cnt;
	}
}

public class Main {
	public static void main(String args[]) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int T = Integer.parseInt(br.readLine());
		int ans;
		for(int i=0; i<T; i++) {
			ans=0;
			Queue<xy> bfs = new LinkedList<>();
			int N = Integer.parseInt(br.readLine()); // 체스판 크기
			 st = new StringTokenizer(br.readLine(), " ");
			int visited[][] = new int[N][N];
			xy now = new xy(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), 0);
			st = new StringTokenizer(br.readLine(), " ");
			xy to = new xy(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), 0);
			
			/* bfs */
			bfs.add(now);
			while(!bfs.isEmpty()) {
				xy pos = bfs.poll();
				if(visited[pos.x][pos.y] ==1 ) continue; 
				if(pos.x == to.x && pos.y == to.y) {
					ans = pos.cnt;
					break;
				}
				visited[pos.x][pos.y]= 1;
				int right = pos.x+1;
				int right_2 = pos.x+2;
				int left = pos.x-1;
				int left_2 = pos.x-2;
				int up = pos.y+1;
				int up_2 = pos.y+2;
				int down = pos.y-1;
				int down_2 = pos.y-2;
				int c = pos.cnt+1;
				if(right<N && up_2<N && visited[right][up_2] == 0)
					bfs.add(new xy(right, up_2, c));
				if(right_2<N && up<N && visited[right_2][up] == 0)
					bfs.add(new xy(right_2, up, c));
				if(right<N && down_2>=0 && visited[right][down_2] == 0)
					bfs.add(new xy(right, down_2, c));
				if(right_2<N && down>=0 && visited[right_2][down] == 0)
					bfs.add(new xy(right_2, down, c));
				if(left>=0 && down_2>=0 && visited[left][down_2] == 0)
					bfs.add(new xy(left, down_2, c));
				if(left_2>=0 && down>=0 && visited[left_2][down] == 0)
					bfs.add(new xy(left_2, down, c));
				if(left>=0 && up_2<N && visited[left][up_2] == 0)
					bfs.add(new xy(left, up_2, c));
				if(left_2>=0 && up<N && visited[left_2][up] == 0)
					bfs.add(new xy(left_2, up, c));
			}
			System.out.println(ans);
		}
	}
}

[개선]

if문의 반복으로 코드가 더러워(?)보인다.

반복문으로 개선할 여지가 있다.

 

GitHub에 티스토리에 올리지 않은 코드들도 업로드 되어 있습니다.

https://github.com/MOBUMIN/BJalgorithm/blob/master/07000-07999/chess_7562.java

MOBUMIN/BJalgorithm