[알고리즘] Java / 백준 / 말이 되고픈 원숭이 / 1600
[알고리즘] Java / 백준 / 말이 되고픈 원숭이 / 1600
문제
접근 방식
3차원 visited배열을 사용하여 말 이동 가능 횟수까지의 방문을 처리하고 bfs로 목표지점까지 탐색한다
코드
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.IOException;
public class Main_1600_정현명 {
static int K,W,H;
static boolean[][] map;
static boolean visited[][][];
static int[][] horseMove = {{2,1},{1,2},{-1,2},{-2,1},{-2,-1},{-1,-2},{1,-2},{2,-1}};
static int[][] monkeyMove = {{-1,0},{0,1},{1,0},{0,-1}};
static int mvCnt = Integer.MAX_VALUE;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
K= Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
W = Integer.parseInt(st.nextToken());
H = Integer.parseInt(st.nextToken());
map = new boolean[H][W];
for(int r=0;r<H;r++) {
st = new StringTokenizer(br.readLine());
for(int c=0;c<W;c++) {
if(Integer.parseInt(st.nextToken())==1) map[r][c] = true;
}
}
bfs();
}
public static void bfs() {
visited = new boolean[H][W][K+1];
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[] {0,0,0,0});
visited[0][0][0] = true;
while(!queue.isEmpty()){
int[] info = queue.poll();
int r= info[0];
int c= info[1];
int k= info[2];
int moveCnt = info[3];
if(r == H-1 && c == W-1) {
System.out.println(moveCnt);
return;
}
// 원숭이 동작으로 이동하기
for(int i=0;i<4;i++) {
int nextR = r + monkeyMove[i][0];
int nextC = c + monkeyMove[i][1];
if(nextR < 0 || nextR >= H || nextC < 0 || nextC >= W || visited[nextR][nextC][k] || map[nextR][nextC]) continue;
visited[nextR][nextC][k] = true;
queue.add(new int[] {nextR,nextC,k,moveCnt+1});
}
// 말 동작으로 이동하기
if(++k<=K) {
for(int i=0;i<8;i++) {
int nextR = r + horseMove[i][0];
int nextC = c + horseMove[i][1];
if(nextR < 0 || nextR >= H || nextC < 0 || nextC >= W || visited[nextR][nextC][k] || map[nextR][nextC]) continue;
visited[nextR][nextC][k] = true;
queue.add(new int[] {nextR,nextC,k,moveCnt+1});
}
}
}
System.out.println(-1);
return;
}
}
Author And Source
이 문제에 관하여([알고리즘] Java / 백준 / 말이 되고픈 원숭이 / 1600), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@gandi0330/알고리즘-Java-백준-말이-되고픈-원숭이-1600저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)