[BOJ] 1600 말이 되고픈 원숭이 (Java)
https://www.acmicpc.net/problem/1600
알고리즘
BFS
참고
풀이
모든 좌표에서 원숭이의 이동횟수를 완전탐색한다.
최단 거리를 구해야하므로 BFS를 적용한다.
말처럼 이동한 횟수를 고려해야하므로 3차원 visited 배열을 이용한다.
코드
import java.io.*;
import java.util.*;
public class Main {
static int K, COUNT, W, H, pan[][];
static boolean[][][] v;
static int[] jumpy = {-1, -2, -2, -1, 1, 2, 2, 1};
static int[] jumpx = {-2, -1, 1, 2, 2, 1, -1, -2};
static int[] dy = {1, -1, 0, 0};
static int[] dx = {0, 0, -1, 1};
static Queue<Monkey> q;
static class Monkey{
int y;
int x;
int cnt;
int k;
public Monkey(int y, int x, int cnt, int k) {
super();
this.y = y;
this.x = x;
this.cnt = cnt;
this.k = k;
}
}
public static void main(String[] args) throws Exception {
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
K = Integer.parseInt(br.readLine());
st = new StringTokenizer(br.readLine());
W = Integer.parseInt(st.nextToken());
H = Integer.parseInt(st.nextToken());
pan = new int[H][W];
v = new boolean[K+1][H][W];
for(int i=0; i<H; i++) {
st = new StringTokenizer(br.readLine());
for(int j=0; j<W; j++) {
pan[i][j] = Integer.parseInt(st.nextToken());
}
}
q = new ArrayDeque<>();
q.offer(new Monkey(0, 0, 0, 0)); // 0, 0 위치에 있는 원숭이를 큐에 넣고 시작
while(!q.isEmpty()) {
Monkey monkey = q.poll(); // 원숭이를 큐에서 빼고
if(monkey.y==H-1 && monkey.x==W-1) { // 원숭이가 pan의 마지막 좌표에 위차한다면 cnt값을 출력하고 종료
System.out.println(monkey.cnt);
return;
}
for(int d=0; d<4; d++) { // 상하좌우 4방탐색 시작
int ny = monkey.y+dy[d]; // 이동할 행 인덱스
int nx = monkey.x+dx[d]; // 이동할 열 인덱스
int cnt = monkey.cnt; // 현재 원숭이가 이동한 횟수
int k = monkey.k; // 현재 원숭이가 말처럼 이동한 횟수
if(ny<0||ny>=H || nx<0||nx>=W || pan[ny][nx]==1 || v[k][ny][nx]) continue;
// 이동할 위치(ny, nx)가 pan의 범위 내이고, 이동할 수 있는 좌표이면서,
// 말처럼 k번 이동했을 때, (ny,nx)가 방문되지 않았다면 진행
v[k][ny][nx] = true; // 말처러 k번 이동했을 때의 pan의 (ny, nx)를 방문처리
q.offer(new Monkey(ny, nx, cnt+1, k)); // ny, nx, 이동횟수+1, 말처럼이동횟수로 초기화된 원숭이를 큐에 추가
}
if(monkey.k == K) continue; // 만약 K만큼 말처럼 이동했다면 아래 코드 진행 x
for(int d=0; d<8; d++) { // 말처럼 이동 8방탐색
int ny = monkey.y+jumpy[d]; // 말처럼 이동할 경우 다음 행 위치
int nx = monkey.x+jumpx[d]; // 말처럼 이동할 경우 다음 열 위치
int cnt = monkey.cnt; // 원숭이가 이동한 횟수
int k = monkey.k + 1; // 말처럼 이동했으므로, 이전 위치에서의 원숭이의 k값에 1을 더한값으로 초기화
if(ny<0||ny>=H || nx<0||nx>=W || pan[ny][nx]==1 || v[k][ny][nx]) continue;
// 이동할 위치(ny, nx)가 pan의 범위 내이고, 이동할 수 있는 좌표이면서,
// 말처럼 k번 이동했을 때, (ny,nx)가 방문되지 않았다면 진행
v[k][ny][nx] = true; // 방문처리
q.offer(new Monkey(ny, nx, cnt+1, k)); // 원숭이 좌표 업데이트
}
}
System.out.println(-1);
br.close();
}
}
Author And Source
이 문제에 관하여([BOJ] 1600 말이 되고픈 원숭이 (Java)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kimdon17/BOJ-1600-말이-되고픈-원숭이-Java저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)