백준 1600 <말이 되고픈 원숭이>

기존의 BFS 방법에서 조금 어려워진 탐색 문제이다. 고려해야 할 점은 BFS탐색을 하면서 말처럼 이동하는 횟수가 K번 이내, 나머지는 원숭이처럼 이동해서 목적지로 이동할 수 있는지 체크를 하는 문제이다.

 

https://skygood95.tistory.com/2 

백준 2206 <벽 부수고 이동하기>

이전의 이 문제에서 조금 더 업그레이드 된 문제라고 보면 되겠다.

전체 맵의 범위가 200*200 총 40000번 그리고 k가 최대 20이기 때문에 800000 즉 80만 번 이기 때문에 시간이 많이 걸리지 않으니 이 방법으로도 충분히 해결할 수 있는 문제이다.

처음에 생각했던 방법은 visit배열을 기존과 같이 이차원 배열로 만들어 기본 Queue를 사용하거나 우선순위 큐를 사용하는 것이었는데 어떤 것을 기준으로 해야 할지에 방법이 없었기 때문에 이전의 방법을 사용하기로 했다.

 

또한 다른 방법은 visit 이차원 배열을 원숭이처럼 이동할 때는 1로 표시하고 말처럼 이동할때는 2로 표시해서 처리해주고 두 가지 방법으로 도달했을 경우 3으로 바꿔주는 방법 또한 있을 것이다. 이렇게 하면 내가 풀어준 문제보다 메모리를 더 최소화할 수 있다. 

 

현재 원숭이의 위치를 나타낼 x좌표 y좌표, 최소의 시간을 입력할 t와 몇 번 말처럼 이동했는가를 나타내기 위한 num 변수를 클래스에 추가했다.

 

그러고 나서 시작 위치와 시간, 말처럼 이동 횟수를 0으로 설정해 queue에 넣어 BFS 탐색을 했다.

 

 

이렇게 BFS탐색을 하면서 Queue에서 제거한 값의 num값이 k가 넘지 않으면 말처럼 이동이 가능하게 하고 그렇지 않다면 원숭이처럼 이동만 가능하게 해서 visit 3차원 배열에 추가해 결과가 나오게 했다.

 

전체 코드

import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main{

	public static class monkey{
		int x;
		int y;
		int num;
		int t;
		public monkey(int x, int y, int num,int t) {
			this.x = x;
			this.y = y;
			this.num = num;
			this.t=t;
		}
	}
	static int k,n,m,result=-1, visit[][][],map[][],dir[][]= {{-1,0},{0,1},{1,0},{0,-1}},mon[][]= {{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1}};
	static Queue<monkey> q;

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader kb = new BufferedReader(new InputStreamReader(System.in));
		k= Integer.parseInt(kb.readLine());
		StringTokenizer st=new StringTokenizer(kb.readLine());
		m = Integer.parseInt(st.nextToken());
		n = Integer.parseInt(st.nextToken());
		visit = new int[n][m][k+1];
		map=new int [n][m];
		q=new LinkedList<monkey>();
		for(int i=0;i<n;i++) {
			st=new StringTokenizer(kb.readLine());
			for(int j=0;j<m;j++) {
				map[i][j]=Integer.parseInt(st.nextToken());
			}
		}
		q.add(new monkey(0,0,0,0));
		visit[0][0][0]=1;
		bfs();
		System.out.println(result);
	}

	public static void bfs() {
		while (!q.isEmpty()) {
			monkey next = q.remove();
			if(next.x==n-1&&next.y==m-1) {
				result=next.t;
				return;
			}
			for (int i = 0; i < 4; i++) {
				int x1=next.x+dir[i][0];
				int y1=next.y+dir[i][1];
				if(x1>=0&&x1<n&&y1>=0&&y1<m&&map[x1][y1]==0
                   &&visit[x1][y1][next.num]==0) {
					visit[x1][y1][next.num]=1;
					q.add(new monkey(x1,y1,next.num,next.t+1));
				}
			}
			if (next.num<k) {
				for (int i = 0; i < 8; i++) {
					int x1=next.x+mon[i][0];
					int y1=next.y+mon[i][1];
					if(x1>=0&&x1<n&&y1>=0&&y1<m&&map[x1][y1]==0
                       &&visit[x1][y1][next.num+1]==0) {
						visit[x1][y1][next.num+1]=1;
						q.add(new monkey(x1,y1,next.num+1,next.t+1));
					}
				}
			}
			
		}
	}
}