[백준(Baekjoon)][자바(java)] 7562 : 나이트의 이동 / DFS와 BFS

 

www.acmicpc.net/problem/7562

7562번: 나이트의 이동

 

문제 풀이

 

import java.io.*;
import java.util.*;

public class Main {

	public static void main(String[] args) throws IOException {
	
		BufferedReader br = new BufferedReader( new InputStreamReader( System.in ) );
		StringTokenizer st;
		Queue<int[]> q;
		StringBuilder sb = new StringBuilder();
		int t = Integer.parseInt( br.readLine() ), n, 
		    s[] = new int[2], e[] = new int[2], a[];
		int dx[] = { -2, -2, 2, 2, -1, -1, 1, 1 }, 
		    dy[] = { 1, -1, 1, -1, 2, -2, 2, -2 }, i, j, c, x, y, nx, ny;
		int dp[][];
		boolean v[][];
		final int max = 90000;
		while( t-- > 0 ) {
			n = Integer.parseInt( br.readLine() );
			st = new StringTokenizer( br.readLine() );
			s[0] = Integer.parseInt( st.nextToken() );
			s[1] = Integer.parseInt( st.nextToken() );
			st = new StringTokenizer( br.readLine() );
			e[0] = Integer.parseInt( st.nextToken() );
			e[1] = Integer.parseInt( st.nextToken() );
			v = new boolean[n][n];
			dp = new int[n][n];
			for( i = 0; i < n; i++ )
				for( j = 0; j < n; j++ )
					dp[i][j] = max;
			dp[s[0]][s[1]] = 0;
			q = new LinkedList<>();
			q.add( new int[] { s[0], s[1] } );
			while( !q.isEmpty() ) {
				a = q.remove();
				x = a[0];  y = a[1];
				if( x == e[0] && y == e[1] )
					continue;
				for( i = 0; i < 8; i++ ) {
					nx = x + dx[i];
					ny = y + dy[i];
					if( nx < 0 || nx >= n || ny < 0 || ny >= n )
						continue;
					if( !v[nx][ny] ) {
						q.add( new int[] { nx, ny } );
						v[nx][ny] = true;
						dp[nx][ny] = Math.min( dp[nx][ny], dp[x][y] + 1 );
					}
				}
			}
			c = dp[e[0]][e[1]];
			sb.append( ( c == max ? 0 : c ) + "\n" );
		}
		br.close();
		System.out.println( sb.toString() );
	}
}

 

*  BFS, DP

-  나이트의 현재 위치가 ( x, y )일 때,
   이동할 수 있는 위치는 ( x-2, y+1 ), ( x-2, y-1 ), ( x+2, y+1 ), ( x+2, y-1 ),
                                 ( x-1, y+2 ), ( x-1, y-2 ), ( x+1, y+2 ), ( x+1, y-2 )
   이를 토대로 dx[], dy[] 배열 생성
-  보드판의 한 변의 길이가 n이므로, n*n 크기의 dp[][] 배열 생성 
   dp[i][j] => 출발 위치에서 ( i, j )의 위치로 가는 최소 이동 횟수
-  boolean v[][] 배열 생성하여 방문하지 않은 지점만 queue에 넣어가며 탐색 횟수 줄임 ( visited ) 
-  출발 지점을 ( s[0], s[1] )라고 할 때, dp[s[0]][s[1]]는 0이 된다. 나머지는 max값으로 초기화
-  이동가능한 위치로 BFS를 하며 최소 이동횟수 갱신
-  도착지점 ( e[0], e[1] )까지 가는 최소 이동 횟수는 dp[e[0]][e[1]] 이다.
   max값( => 이동 불가능 )이면 정답은 0이 된다
-  케이스마다 반복