[BFS] 백준 - 나이트의 이동

https://www.acmicpc.net/problem/7562

7562번: 나이트의 이동

 

-문제해설

전형적인 BFS문제이다. 그래프 이동을 위해서 dx, dy 배열을 지정하고 반복문을 돌면서 좌표를 이동시킨다.

이때 중요한 점은 이동횟수를 큐에 같이 집어넣어줘야한다. 

 

이를 위해서 Point 사용자 클래스를 정의하고 필드값은 x, y, ans 이다. ans는 이동횟수를 나타내는 변수이다.

 

자세한 내용은 아래 코드 참고

 

 

-자바

package bfs_dfs;

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 Point {
	int x, y, ans;
	Point( int x, int y ) {
		this.x = x;
		this.y = y;
		ans = 0;
	}
	
	Point( int x, int y, int ans ) {
		this.x = x;
		this.y = y;
		this.ans = ans;
	}
}

public class BJ7562 {
	private static int[][] arr;
	private static int[][] visit;
	private static int l;
	private static int[] dx = { -1, -1, -2, -2,  1, 1,  2, 2 };
	private static int[] dy = { -2,  2, -1,  1, -2, 2, -1, 1};
	
	private static String bfs( int x, int y ) {
		Queue<Point> que = new LinkedList<Point>();
		que.offer( new Point(x, y) );
		visit[x][y] = 1;
		
		int new_x, new_y;
		while( !que.isEmpty() ) {
			Point p = que.poll();
			if( arr[p.x][p.y] == 1 ) return p.ans + "";
			
			for( int i=0; i<8; i++ ) {
				new_x = p.x + dx[i];
				new_y = p.y + dy[i];
				
				if( new_x < 0 || new_y < 0 || new_x >= l || new_y >= l ) 
					continue;
				
				if( visit[new_x][new_y] != 1 ) {
					visit[new_x][new_y] = 1;
					que.offer( new Point( new_x, new_y, p.ans+1 ) );
					
				}
			}
		}
	
		return "";
	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt( br.readLine() );
		
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		int x, y;
		while( t --> 0 ) {
			l = Integer.parseInt( br.readLine() );
			
			arr = new int[l][l];
			visit = new int[l][l];
			st = new StringTokenizer( br.readLine() );
			x = Integer.parseInt( st.nextToken() );
			y = Integer.parseInt( st.nextToken() );
			
			st = new StringTokenizer( br.readLine() );
			arr[Integer.parseInt(st.nextToken())][Integer.parseInt(st.nextToken())] = 1;
			
			sb.append( bfs( x, y ) ).append( "\n" );
		}
		
		System.out.println( sb );
	}
}

 

-파이썬

from collections import deque

dx = [ -1, -1, -2, -2,  1, 1,  2, 2 ]
dy = [ -2,  2, -1,  1, -2, 2, -1, 1 ]

def bfs( a, b, arr ):
    que = deque()
    vis[a][b] = 1
    
    ans = 0
    que.append( [a, b, ans] )
    
    while que:
        tmp = que.popleft()
        
        if arr[ tmp[0] ][ tmp[1] ] == 1:
            return tmp[2]
        
        for i in range( 8 ):
            n_x = tmp[0] + dx[i]
            n_y = tmp[1] + dy[i]
            

            if n_x < 0 or n_y < 0 or n_x >= len(arr) or n_y >= len(arr):
                continue
            
            if vis[n_x][n_y] != 1:
                vis[n_x][n_y] = 1
                que.append( [ n_x, n_y, tmp[2]+1 ] )

t = int( input() )

for _ in range( t ):
    n = int( input() )
    
    arr = list( [0]*n for _ in range( n ) )
    vis = list( [0]*n for _ in range( n ) )
    a, b = map(int, input().split())
    x, y = map(int, input().split())
    arr[x][y] = 1
    print( bfs( a, b, arr ) )