[Algorithm] ๐Ÿ’๋ฐฑ์ค€ 1600 ๋ง์ด ๋˜๊ณ ํ”ˆ ์›์ˆญ์ด

37813 ๋‹จ์–ด ๋ฐฑ์ค€BFSBFS

0. ๋ฌธ์ œ

๋™๋ฌผ์›์—์„œ ๋ง‰ ํƒˆ์ถœํ•œ ์›์ˆญ์ด ํ•œ ๋งˆ๋ฆฌ๊ฐ€ ์„ธ์ƒ๊ตฌ๊ฒฝ์„ ํ•˜๊ณ  ์žˆ๋‹ค. ๊ทธ ๋…€์„์€ ๋ง(Horse)์ด ๋˜๊ธฐ๋ฅผ ๊ฐ„์ ˆํžˆ ์›ํ–ˆ๋‹ค. ๊ทธ๋ž˜์„œ ๊ทธ๋Š” ๋ง์˜ ์›€์ง์ž„์„ ์œ ์‹ฌํžˆ ์‚ดํŽด๋ณด๊ณ  ๊ทธ๋Œ€๋กœ ๋”ฐ๋ผ ํ•˜๊ธฐ๋กœ ํ•˜์˜€๋‹ค. ๋ง์€ ๋ง์ด๋‹ค. ๋ง์€ ๊ฒฉ์žํŒ์—์„œ ์ฒด์Šค์˜ ๋‚˜์ดํŠธ์™€ ๊ฐ™์€ ์ด๋™๋ฐฉ์‹์„ ๊ฐ€์ง„๋‹ค. ๋‹ค์Œ ๊ทธ๋ฆผ์— ๋ง์˜ ์ด๋™๋ฐฉ๋ฒ•์ด ๋‚˜ํƒ€๋‚˜์žˆ๋‹ค. xํ‘œ์‹œํ•œ ๊ณณ์œผ๋กœ ๋ง์ด ๊ฐˆ ์ˆ˜ ์žˆ๋‹ค๋Š” ๋œป์ด๋‹ค. ์ฐธ๊ณ ๋กœ ๋ง์€ ์žฅ์• ๋ฌผ์„ ๋›ฐ์–ด๋„˜์„ ์ˆ˜ ์žˆ๋‹ค.

๊ทผ๋ฐ ์›์ˆญ์ด๋Š” ํ•œ ๊ฐ€์ง€ ์ฐฉ๊ฐํ•˜๊ณ  ์žˆ๋Š” ๊ฒƒ์ด ์žˆ๋‹ค. ๋ง์€ ์ €๋ ‡๊ฒŒ ์›€์ง์ผ ์ˆ˜ ์žˆ์ง€๋งŒ ์›์ˆญ์ด๋Š” ๋Šฅ๋ ฅ์ด ๋ถ€์กฑํ•ด์„œ ์ด K๋ฒˆ๋งŒ ์œ„์™€ ๊ฐ™์ด ์›€์ง์ผ ์ˆ˜ ์žˆ๊ณ , ๊ทธ ์™ธ์—๋Š” ๊ทธ๋ƒฅ ์ธ์ ‘ํ•œ ์นธ์œผ๋กœ๋งŒ ์›€์ง์ผ ์ˆ˜ ์žˆ๋‹ค. ๋Œ€๊ฐ์„  ๋ฐฉํ–ฅ์€ ์ธ์ ‘ํ•œ ์นธ์— ํฌํ•จ๋˜์ง€ ์•Š๋Š”๋‹ค.

์ด์ œ ์›์ˆญ์ด๋Š” ๋จธ๋‚˜๋จผ ์—ฌํ–‰๊ธธ์„ ๋– ๋‚œ๋‹ค. ๊ฒฉ์žํŒ์˜ ๋งจ ์™ผ์ชฝ ์œ„์—์„œ ์‹œ์ž‘ํ•ด์„œ ๋งจ ์˜ค๋ฅธ์ชฝ ์•„๋ž˜๊นŒ์ง€ ๊ฐ€์•ผํ•œ๋‹ค. ์ธ์ ‘ํ•œ ๋„ค ๋ฐฉํ–ฅ์œผ๋กœ ํ•œ ๋ฒˆ ์›€์ง์ด๋Š” ๊ฒƒ, ๋ง์˜ ์›€์ง์ž„์œผ๋กœ ํ•œ ๋ฒˆ ์›€์ง์ด๋Š” ๊ฒƒ, ๋ชจ๋‘ ํ•œ ๋ฒˆ์˜ ๋™์ž‘์œผ๋กœ ์นœ๋‹ค. ๊ฒฉ์žํŒ์ด ์ฃผ์–ด์กŒ์„ ๋•Œ, ์›์ˆญ์ด๊ฐ€ ์ตœ์†Œํ•œ์˜ ๋™์ž‘์œผ๋กœ ์‹œ์ž‘์ง€์ ์—์„œ ๋„์ฐฉ์ง€์ ๊นŒ์ง€ ๊ฐˆ ์ˆ˜ ์žˆ๋Š” ๋ฐฉ๋ฒ•์„ ์•Œ์•„๋‚ด๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค.

์ž…๋ ฅ
์ฒซ์งธ ์ค„์— ์ •์ˆ˜ K๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๋‘˜์งธ ์ค„์— ๊ฒฉ์žํŒ์˜ ๊ฐ€๋กœ๊ธธ์ด W, ์„ธ๋กœ๊ธธ์ด H๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๊ทธ ๋‹ค์Œ H์ค„์— ๊ฑธ์ณ W๊ฐœ์˜ ์ˆซ์ž๊ฐ€ ์ฃผ์–ด์ง€๋Š”๋ฐ, 0์€ ์•„๋ฌด๊ฒƒ๋„ ์—†๋Š” ํ‰์ง€, 1์€ ์žฅ์• ๋ฌผ์„ ๋œปํ•œ๋‹ค. ์žฅ์• ๋ฌผ์ด ์žˆ๋Š” ๊ณณ์œผ๋กœ๋Š” ์ด๋™ํ•  ์ˆ˜ ์—†๋‹ค. ์‹œ์ž‘์ ๊ณผ ๋„์ฐฉ์ ์€ ํ•ญ์ƒ ํ‰์ง€์ด๋‹ค. W์™€ H๋Š” 1์ด์ƒ 200์ดํ•˜์˜ ์ž์—ฐ์ˆ˜์ด๊ณ , K๋Š” 0์ด์ƒ 30์ดํ•˜์˜ ์ •์ˆ˜์ด๋‹ค.

์ถœ๋ ฅ
์ฒซ์งธ ์ค„์— ์›์ˆญ์ด์˜ ๋™์ž‘์ˆ˜์˜ ์ตœ์†Ÿ๊ฐ’์„ ์ถœ๋ ฅํ•œ๋‹ค. ์‹œ์ž‘์ ์—์„œ ๋„์ฐฉ์ ๊นŒ์ง€ ๊ฐˆ ์ˆ˜ ์—†๋Š” ๊ฒฝ์šฐ์—” -1์„ ์ถœ๋ ฅํ•œ๋‹ค.

1. ์•„์ด๋””์–ด

๐Ÿ’ก ๋ง์ฒ˜๋Ÿผ ์ด๋™ํ•œ ํšŸ์ˆ˜๋ฅผ ์ €์žฅํ•˜๋Š” k์™€ ์ตœ์†Œ ํšŸ์ˆ˜๋ฅผ ์ €์žฅํ•˜๋Š” cnt๋ฅผ ํฌํ•จํ•œ Node class ์ƒ์„ฑ
๐Ÿ’ก k๋ฅผ ๋ช‡๋ฒˆ ์‚ฌ์šฉํ–ˆ๋Š”์ง€๋ฅผ ์ €์žฅํ•˜๋Š” visited[][][]๋ฅผ ์‚ฌ์šฉ
๐Ÿ’ก k๋ฅผ ๋„˜์ง€ ์•Š์œผ๋ฉด, ๋ง์ฒ˜๋Ÿผ ์ด๋™
๐Ÿ’ก ๊ธฐ๋ณธ์ ์œผ๋กœ ์›์ˆญ์ด์ฒ˜๋Ÿผ ์ด๋™
๐Ÿ’ก ๋งˆ์ง€๋ง‰ ์นธ์— ๋„๋‹ฌํ•˜๋ฉด queue์—์„œ pollํ•œ cnt๊ฐ’์„ ์ถœ๋ ฅํ•จ

2. ํ•ต์‹ฌ ํ’€์ด

  1. ๋ง์ฒ˜๋Ÿผ ์ด๋™ํ•œ ํšŸ์ˆ˜๋ฅผ ์ €์žฅํ•˜๋Š” k์™€ ์ตœ์†Œ ํšŸ์ˆ˜๋ฅผ ์ €์žฅํ•˜๋Š” cnt๋ฅผ ํฌํ•จํ•œ Node class ์ƒ์„ฑ
static class Node{
	int x;
	int y;
	int cnt;
	int k;
	Node(int x, int y, int cnt, int k){
		this.x = x;
		this.y = y;
		this.cnt = cnt;
		this.k = k;
	}
}
  1. k๋ฅผ ๋ช‡๋ฒˆ ์‚ฌ์šฉํ–ˆ๋Š”์ง€๋ฅผ ์ €์žฅํ•˜๋Š” visited[][][]๋ฅผ ์‚ฌ์šฉ
static boolean[][][] visited;
  1. k๋ฅผ ๋„˜์ง€ ์•Š์œผ๋ฉด, ๋ง์ฒ˜๋Ÿผ ์ด๋™
if(now.k < k) {
	for(int i=0; i<8; i++) {
		int nx = now.x + dx1[i];
		int ny = now.y + dy1[i];
					
		if(nx >= h || ny >= w || nx<0 || ny<0)
			continue;
					
		if(board[nx][ny] != 1 && visited[nx][ny][now.k+1] == false) {
			q.add(new Node(nx, ny, now.cnt+1, now.k+1));
			visited[nx][ny][now.k+1] = true;
		}
	}
}
  1. ๊ธฐ๋ณธ์ ์œผ๋กœ ์›์ˆญ์ด์ฒ˜๋Ÿผ ์ด๋™
for(int i=0; i<4; i++) {
	int nx = now.x + dx2[i];
	int ny = now.y + dy2[i];
				
	if(nx >= h || ny >= w || nx < 0 || ny < 0)
		continue;
				
	if(board[nx][ny] != 1 && visited[nx][ny][now.k] == false) {
		q.add(new Node(nx, ny, now.cnt+1, now.k));
		visited[nx][ny][now.k] = true;
	}
}
  1. ๋งˆ์ง€๋ง‰ ์นธ์— ๋„๋‹ฌํ•˜๋ฉด queue์—์„œ pollํ•œ cnt๊ฐ’์„ ์ถœ๋ ฅํ•จ
if(now.x == h-1 && now.y == w-1) {
	res = now.cnt;
	break;
}
...
System.out.println(res);

3. ์ฝ”๋“œ

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Queue;
import java.util.LinkedList;

public class Bruteforce_5 {
	static int[] dx1 = {-1,1,-2,2,-2,2,-1,1};
	static int[] dx2 = {0,0,-1,1};
	static int[] dy1 = {2,2,1,1,-1,-1,-2,-2};
	static int[] dy2 = {-1,1,0,0};
	static int[][] board;
	static boolean[][][] visited; 
	static int k,w,h;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		k = Integer.parseInt(br.readLine());
		
		String[] s = br.readLine().split(" ");
		w = Integer.parseInt(s[0]);
		h = Integer.parseInt(s[1]);
		
		board = new int[h][w];
		visited = new boolean[h][w][k+1];
		
		for(int i=0; i<h; i++) {
			s = br.readLine().split(" ");
			for(int j=0; j<w; j++) {
				board[i][j] = Integer.parseInt(s[j]);
			}
		}
		
		bfs();
	}
	
	static void bfs() {
		Queue<Node> q = new LinkedList<>();
		int res = -1;
		q.add(new Node(0,0,0,0));
		visited[0][0][0] = true;
		
		while(!q.isEmpty()) {
			Node now = q.poll();
			
			if(now.x == h-1 && now.y == w-1) {
				res = now.cnt;
				break;
			}
			
			if(now.k < k) {
				for(int i=0; i<8; i++) {
					int nx = now.x + dx1[i];
					int ny = now.y + dy1[i];
					
					if(nx >= h || ny >= w || nx<0 || ny<0)
						continue;
					
					if(board[nx][ny] != 1 && visited[nx][ny][now.k+1] == false) {
						q.add(new Node(nx, ny, now.cnt+1, now.k+1));
						visited[nx][ny][now.k+1] = true;
					}
				}
			}
			
			for(int i=0; i<4; i++) {
				int nx = now.x + dx2[i];
				int ny = now.y + dy2[i];
				
				if(nx >= h || ny >= w || nx < 0 || ny < 0)
					continue;
				
				if(board[nx][ny] != 1 && visited[nx][ny][now.k] == false) {
					q.add(new Node(nx, ny, now.cnt+1, now.k));
					visited[nx][ny][now.k] = true;
				}
			}
		}
		
		System.out.println(res);
	}
	
	static class Node{
		int x;
		int y;
		int cnt;
		int k;
		Node(int x, int y, int cnt, int k){
			this.x = x;
			this.y = y;
			this.cnt = cnt;
			this.k = k;
		}
	}

}

4. ๊ฒฐ๊ณผ

์„ฑ๊ณตโœจ

์ข‹์€ ์›นํŽ˜์ด์ง€ ์ฆ๊ฒจ์ฐพ๊ธฐ