백준 16948(데스나이트) - Python(파이썬),자바(Java)

16948번: 데스 나이트

BFS - duque 메서드 - Python(파이썬),Java(자바)

풀이 방법

① 이차원 배열로 nxn graph 생성 ( -> 이동 거리를 표현하는 그래프) 

② bfs 방식으로 큐 안에 값이 없어질 때까지 처음 시작점 (r1,c1)에서 갈수 있는 점의 모든 리스트의 값을 변경 , 이 때 변경 시에는 방금 시작점의 graph의 값(graph[r1][c1]) +1 

# BFS
import sys
from collections import deque

# 체스판의 크기 입력 받기
n = int(sys.stdin.readline())
# 체스판에 모든 값을 0으로 설정해서 만들기
graph = [[0 for _ in range(n)] for _ in range(n)]
# r1,c1,r2,c2 입력 받기
r1, c1, r2, c2 = map(int, sys.stdin.readline().split())

# 데스나이트가 이동할 수 있는 방법
dr = [-2, -2, 0, 0, 2, 2]
dc = [-1, 1, -2, 2, -1, 1]


def bfs(r1, c1):
    # 큐 구현
    queue = deque()
    # 큐에 r1,c2 집어 넣기
    queue.append((r1, c1))
    while queue:  # 큐가 빌때까지
        r1, c1 = queue.popleft()  # 큐에서 꺼냄
        for i in range(6):
            nr = r1 + dr[i]
            nc = c1 + dc[i]
            # 넣은 값이 체스판을 넘어 가는 경우 무시
            if nr < 0 or nc < 0 or nr >= n or nc >= n:
                continue
            # 체스판에 처음 접근 한 경우에만 방금 있었던 이동 거리 +1 && 큐에 삽입
            if graph[nr][nc] == 0:
                graph[nr][nc] = graph[r1][c1] + 1
                queue.append((nr, nc))


# 함수 실행
bfs(r1, c1)
# 시작점으로부터 갈 수 없는 경우에는 0이 설정되어 있으므로 0인 경우 -1 출력
if graph[r2][c2] == 0:
    print(-1)
else:
    print(graph[r2][c2])

약간의 수정 

※ dr,dc를 다르게 받았다면 ->  d =[(-2,-1),,,,,,]  for dr,dc in d:이렇게 for문 사용

※ 위에서는 그래프의 초기값을 0으로 설정했다면 밑에서는 -1로 처음부터 설정한 후에 bfs를 실행 시 graph의 값을 0으로 변경한다.

#BFS
import sys
from collections import deque

#체스판의 크기 입력 받기
n = int(sys.stdin.readline())
#체스판에 모든 값을 -1으로 설정해서 만들기
graph = [[-1 for _ in range(n)] for _ in range(n)]
#r1,c1,r2,c2 입력 받기
r1,c1,r2,c2=map(int,sys.stdin.readline().split())

#데스나이트가 이동할 수 있는 방법
d = [(-2, -1), (-2, 1), (0, -2), (0, 2), (2, -1), (2, 1)]

def bfs(r1,c1):
    #큐 구현
    queue = deque()
    #큐에 r1,c2 집어 넣기
    queue.append((r1,c1))
    #0으로 설정
    graph[r1][c1]=0
    while queue:#큐가 빌때까지
        r1,c1 = queue.popleft()#큐에서 꺼냄
        for dr,dc in d:
            nr = r1+dr
            nc = c1+dc
            #넣은 값이 체스판을 넘어 가는 경우 무시
            if nr<0 or nc<0 or nr>=n or nc>=n:
                continue
            #체스판에 처음 접근 한 경우에만 방금 있었던 이동 거리 +1 && 큐에 삽입
            if graph[nr][nc]==-1:
                graph[nr][nc]=graph[r1][c1]+1
                queue.append((nr,nc))

#함수 실행
bfs(r1,c1)
print(graph[r2][c2])

---

자바로 푼 경우 

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

public class Main {
    static int r1,r2,c1,c2;
    //이차원 배열 설정
    static int n;
    static int[][] graph;
    static int[][] d = {{-2,-1},{-2,1},{0,-2},{0,2},{2,-1},{2,1}};
    static void bfs(int x,int y){
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[] {x,y});
        while(!q.isEmpty()){
            int[] tmp=q.poll();
            graph[x][y]=0;
            for(int drc[]:d){
                int nr = tmp[0]+drc[0];
                int nc = tmp[1]+drc[1];
                if(nr>=0 && nr<n && nc>=0 && nc<n && graph[nr][nc]==-1){
                    graph[nr][nc]=graph[tmp[0]][tmp[1]]+1;
                    q.offer(new int[] {nr,nc});
                }
            }
        }
    }
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        r1 = Integer.parseInt(st.nextToken());
        c1=Integer.parseInt(st.nextToken());
        r2 = Integer.parseInt(st.nextToken());
        c2 = Integer.parseInt(st.nextToken());
        graph=new int[n][n];
        //-1로 모두 초기화
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                graph[i][j]=-1;
            }
        }
        bfs(r1,c1);
        System.out.println(graph[r2][c2]);
    }
}