[백준] 단계별로 풀어보기(단계:24, DFS와BFS,JAVA)7562번, 나이트의 이동

문제 링크

7562번: 나이트의 이동

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

DFS(깊이 우선 탐색)은 아래 그림처럼 어떤 조건을 가지고 목표노드에 도달하기까지 자식노드를 통해 이동하며 목표노드까지 도달하는 것을 말합니다.

자식 노드에 도착하면 그 자식노드에서 조건에 만족하는 자식노드로 다시 이동하여 목표 노드로 이동합니다.

 

출처 : https://ko.wikipedia.org/wiki/%EA%B9%8A%EC%9D%B4_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

BFS(너비 우선 탐색)은 아래 그림처럼 시작 노드에 인접한 노드를 모두 탐색한 후 인접한 노드를 기준으로 다시 인접한 노드를 찾아내는 것을 반복하여 탐색합니다.

시작 노드 탐색이 끝나면 인접했던 노드를 시작 노드로 생각하고 다시 탐색합니다.

출처 : https://ko.wikipedia.org/wiki/%EB%84%88%EB%B9%84_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

더 자세한 내용은 아래 링크에 들어가서 확인해주시면 감사하겠습니다.

DFS

깊이 우선 탐색 - 위키백과, 우리 모두의 백과사전

BFS

너비 우선 탐색 - 위키백과, 우리 모두의 백과사전

이 문제에 핵심은

1. 체스판의 크기, 나이트의 출발 위치, 나이트의 도착 위치가 주어집니다.

2. 나이트는 2칸을 상,하,좌,우로 이동한 뒤 대각선으로 한 번 이동합니다.

3. 목적지까지 가는 최소 이동 횟수를 구해 결과로 출력해야 합니다.

 

저는 BFS(너비우선탐색)을 이용하여 문제를 해결하였습니다.

출발 위치에서부터 나이트가 이동가능한 경로를 탐색하여 처음 목적지에 도착했을 때가 최소 이동 횟수입니다.

나이트의 이동을 탐색하기 위해 dx[]와 dy[]를 사용하였습니다.

 

dx[] = {-1, -2, -2, -1, 1, 2, 2, 1}

 

dy[] = {-2, -1, 1, 2, -2, -1, 1, 2}

 

check배열을 통해서 체스판에 해당 지점을 탐색했는지를 확인하였습니다.

Queue에서 사용할 생성자 coordinate를 만들었으며

 

x = x좌표

 

y = y좌표

 

distance = 이동 거리

 

예제 입력1에서 첫 번쨰 나이트 이동할 때를 BFS로 탐색을 하는 과정을 보여드리겠습니다.

하늘색 = 출발 지점, 보라색 = 도착 지점, 빨간색 = 탐색한 지점, 초록색 = 현재 과정에서 탐색한 지점

0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0

1. (0,0)에서 나이트의 이동 경로를 탐색하였습니다.

 

우측 하단 대각선, 아래측 우측 대각선 이동 가능합니다.

우측 하단 대각선  (1, 2)

x = x + dx[7] = 0 + 1 = 1

y = y + dy[7] = 0 + 2 = 2

아래측 우측 대각선 (2, 1)

x = x + dx[6] = 0 + 2 = 2

y = y + dy[6] = 0 + 1 = 1

0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0

2. 위 과정을 반복하여 얻어지는 결과를 표로 표현해보겠습니다.

0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0

3. 다음....

0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0

4. 다음...

0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0

5. 마지막....

0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0
0(도착점)	0	0	0	0	0	0	0

5번째 과정에서 도착점에 도착한 것을 표로 확인하여 결과로 5를 출력하면 됩니다.

 

문제를 해결한 알고리즘의 과정입니다.

1. 체스판과 나이트에 대한 정보를 저장합니다.

2. BFS(너비 우선 탐색)을 이용하여 나이트의 이동경로로 탐색을 진행합니다.

3. Queue에 생성자를 사용하여 이동거리 및 현재 위치를 저장합니다.

4. 목적지에 도착했을 때 큐에 저장된 distance에 값을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 통해 출발 위치 및 도착 위치를 저장하였습니다.
• 큐에 사용할 coordinate 생성자를 만들었습니다.
• BFS로 도착 위치까지 도착하는 최단 이동 횟수를 구하는 bfs 함수를 만들었습니다.
• BufferedWriter에 최단 이동 횟수를 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• bfs은 board[][],dx[],dy[]와 Queue를 통해 지점을 나이트의 이동을 탐색하였습니다.

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	//------좌표 및 거리를 저장하는 생성자-------
	public static class coordinate{
		int x,y,distance;
		public coordinate(int x, int y, int distance) {
			this.x = x;
			this.y = y;
			this.distance = distance;
		}

		public int getX() {
			return x;
		}

		public int getY() {
			return y;
		}

		public int getDistance() {
			return distance;
		}

	}
	public static int[] dx = {-1, -2, -2, -1, 1, 2, 2, 1 };	//나이트 이동 X 변경값
	public static int[] dy = {-2, -1, 1, 2, -2, -1, 1, 2 };	//나이트 이동 Y 변경값
	public static boolean[][] board;	//체스판
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
        //---------입력값 저장 및 배열 초기화---------
    	StringTokenizer st;
    	int N = Integer.parseInt(br.readLine());
    	for(int i=0;i<N;i++) {
    		int I = Integer.parseInt(br.readLine());
    		board = new boolean[I][I];
    		
    		st = new StringTokenizer(br.readLine()," ");
    		int startX = Integer.parseInt(st.nextToken());
    		int startY = Integer.parseInt(st.nextToken());
    		
    		st = new StringTokenizer(br.readLine()," ");
    		int endX = Integer.parseInt(st.nextToken());
    		int endY = Integer.parseInt(st.nextToken());
    		
    		int result = bfs(startX, startY, endX, endY, I);
    		bw.write(result + "\n");		// 최소 이동 횟수 BufferedWriter 저장
    	}
    	bw.flush();		//결과 저장
    	bw.close();
    	br.close();
    }
    //------BFS로 나이트의 이동 탐색하여 최소 이동 횟수 구하는 함수-----
    public static int bfs(int startX, int startY, int endX, int endY, int boardSize) {
    	Queue<coordinate> queue = new LinkedList<coordinate>();
    	queue.add(new coordinate(startX, startY, 0));	//출발 위치 큐에 저장
    	while(!queue.isEmpty()) {
    		coordinate temp = queue.poll();
    		int x = temp.getX();
    		int y = temp.getY();
    		int distance = temp.getDistance();
    		if(x==endX && y==endY)	//목적지 도착
    			return distance;
    		for(int i=0;i<8;i++) {
    			int tempX = x + dx[i];
    			int tempY = y + dy[i];
    			if(tempX>=0 && tempX<boardSize && tempY>=0 && tempY<boardSize) {
    				if(!board[tempX][tempY]) {	//해당 지역 탐색되지 않았을 때
    					board[tempX][tempY] = true;
    					queue.add(new coordinate(tempX, tempY, distance+1));
    				}
    			}
    		}
    	}
    	return 0;
    }
}