말이 되고픈 원숭이 [백준 1600][JAVA][골드 5][BFS]

 

[광고 누르면 오늘의 행운 상승!!]

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

1600번: 말이 되고픈 원숭이

BFS 시뮬레이션 문제 

원숭이는 말처럼 N번 이동할 수 있다.

1.포인트는 말처럼 이동할 때 3차원 visit배열을 이용하여 방문처리를 하여야 한다.
말처럼 이동할 때와 기본이동이 서로 부딫히는 경우가 있기 때문이다.

2. 0,0 지점에서 bfs를 시작한다.

3. dx,dy배열을 기본이동 + 말의 이동으로 해놓아서 for문을 12번 돈다.

4. i가 4이상일 때는 말처럼 이동할 때 이므로 이동할 수 있는 monkey.jump가 남아있는지 확인한다.

5. 없다면 continue 있다면 3차원 방문처리를 해준다.

6. map[N-1][N-1] 지점(도착지점)에 도달했다면 cnt를 출력한다.

7. 도달하지 못했다면 -1를 출력한다.

package Study5;

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

class Monkey{
	int row, col, jump,cnt;
	public Monkey(int row, int col, int jump,int cnt) {
		this.row = row;
		this.col = col;
		this.jump = jump;
		this.cnt  = cnt;
	}
}
public class 말이되고픈원숭이 {
	static int[] dx = {-1,0,1,0,-1,-2,-2,-1,1,2,2,1};
	static int[] dy = {0,1,0,-1,2,1,-1,-2,-2,-1,1,2};
	static int[][] map;
	static boolean[][][] visit;
	static int N,R,C,ans;
	static Queue<Monkey> q;
	
	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("test.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		C = Integer.parseInt(st.nextToken());
		R = Integer.parseInt(st.nextToken());
		
		map = new int[R][C];
		visit = new boolean[N+1][R][C];
		q =  new LinkedList<>();
		for (int i = 0; i < R; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < C; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		if(0 == R-1 && 0 == C-1) {
			System.out.println(0);
			return;
		}
		System.out.println(bfs());
	}
	private static int bfs() {
		q.add(new Monkey(0,0,N,0));
		visit[N][0][0] = true;
		
		while(!q.isEmpty()) {
			Monkey monkey = q.poll();
			for (int i = 0; i < 12; i++) {
				if(i >= 4 && monkey.jump == 0) break;
				
				int nx = monkey.row + dx[i];
				int ny = monkey.col + dy[i];
				
				if(check(nx, ny) || map[nx][ny] == 1) continue;
				
				
				int jump = (i>=4) ? monkey.jump -1 : monkey.jump;
				
				if(visit[jump][nx][ny]) continue;
				visit[jump][nx][ny] = true;
				
				if(nx == R-1 && ny == C-1) {
					return monkey.cnt+1;
				}
				
				q.add(new Monkey(nx,ny,jump,monkey.cnt+1));
			}
		}
		return -1;
	}
	private static boolean check(int nx, int ny) {
		return nx < 0 || nx >=R || ny < 0 || ny >= C;
	}
}