백준_말이 되고픈 원숭이_1600[Java]

문제

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

1600번: 말이 되고픈 원숭이

 

풀이

BFS로 K가 남았는지 확인해가면서 인접한 칸으로 이동하거나 말처럼 이동하는 경우를 탐색하여 

가장 먼저 목표지점에 도달했을 때의 이동 횟수를 출력한다. 

 

Queue에는 현재 위치 정보(x,y)와 해당 위치에 오기 위해 이동한 횟수(cnt), 그리고 남은 K의 갯수(k)를 담는다. 

 

* 문제점

목표지점에 도달하는 하나의 경로에서 이미 방문한 위치에 재방문하지 않기 위해 방문 기록을 저장하는 2차원 배열(visit)을 선언하였다.

하지만 BFS방식이었기 때문에 탐색하고 있는 현재 경로가 아닌 다른 경로에서 먼저 방문했을 때 현재 경로에서 해당 위치를 방문하지 못하는 문제점이 발생하였다. (다른 경로가 서로의 탐색에 관여하게 됨) 따라서 백준의 질문탭에서 나와 같은 문제에 부딪힌 사람이 있었고 그 덕분에 문제를 해결할 수 있었다. 링크

 

-> 해결방법 

visit을 3차원 배열로 선언한다. 

 

 

아래 두가지 테스트케이스를 만족하면 된다.. !

 

- TEST CASE 01

INPUT : 

4

6 10

0 0 1 1 1 1

0 1 1 0 1 1

0 1 1 1 1 0

0 1 1 1 1 0

0 1 1 1 1 0

0 1 1 1 1 0

0 1 1 0 1 1

0 1 1 1 1 1

1 1 1 1 0 0

1 0 0 1 1 0

OUTPUT : 10 

 

- TEST CASE 02

INPUT : 

1

4 4

0 1 1 1

0 0 1 1

1 0 1 1

1 1 1 0

OUTPUT : 4

 

코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	static int K, W, H;
	static int[][] map;
	static boolean[][][] visit;

	static class Pair{
		int x;
		int y;
		int cnt;
		int k;
		
		Pair(int x, int y, int cnt, int k){
			this.x = x;
			this.y = y;
			this.cnt = cnt;
			this.k = k;
		}
	}
    
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		K = sc.nextInt();
		W = sc.nextInt();
		H = sc.nextInt();
		
		map = new int[H][W];
		visit = new boolean[H][W][31];
		for(int i = 0; i < H; i++) {
			for(int j = 0; j < W; j++) {
				map[i][j] = sc.nextInt();
			}
		}

		visit[0][0][0] = true;
		solution();
		
		sc.close();
	}

	// 동서남북 좌우상하(말)
	static int[] dx = {1,-1, 0, 0};
	static int[] dy = {0, 0, 1, -1}; 
	static int[] hx = {-2, -2, 2, 2, 1, -1, 1, -1};
	static int[] hy = {1, -1, 1, -1, 2, 2, -2, -2};
	private static void solution() {
		Queue<Pair> q = new LinkedList<Pair>();
		q.add(new Pair(0,0,0,K));
		
		while(!q.isEmpty()) {
			Pair cur = q.poll();
			int curX = cur.x;
			int curY = cur.y;
			int cnt = cur.cnt;
			int curK = cur.k;
			
			if(curX == W-1 && curY == H-1) {
				System.out.println(cnt);
				return;
			}
			
			if(curX >= W || curY >= H || curX < 0 || curY < 0) continue;
			if(map[curY][curX] == 1) continue;
			
			if(visit[curY][curX][curK]) continue;
			visit[curY][curX][curK] = true;
			
			for(int i = 0; i < 4; i++) {
				int nextX = curX + dx[i];
				int nextY = curY + dy[i];
				
				q.add(new Pair(nextX, nextY, cnt+1,  curK));
				
			}
			
			if(curK == 0) continue;
			for(int i = 0; i < 8; i++) {
				int nextX = curX + hx[i];
				int nextY = curY + hy[i];
				
				q.add(new Pair(nextX, nextY, cnt+1, curK-1));
				
			}
				
			
		}
		System.out.println("-1");
		return;
		
	}

}

 

참고

- 조건문 정리 어렵다아. 심플하게 작성하심 !

https://debuglog.tistory.com/90

백준 1600번 - 말이 되고픈 원숭이

 

- 반례 및 visit[] 배열을 3차원으로 선언해야하는 이유

https://www.acmicpc.net/board/view/30139

글 읽기 - 왜 틀렸는지 모르겠어요