정올 4189 장기2 (JAVA 자바)

문제 출처 - http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=3539&sca=3040

JUNGOL

 

문제

N×M장기판에 졸 한개와 말 한개가 놓여 있다. 말의 이동 방향이 다음과 같다고 할 때, 말이 최소의 이동횟수로 졸을 잡으려고 한다. 

 

말이 졸을 잡기 위한 최소 이동 횟수를 구하는 프로그램을 작성해보자. 

 

입력형식

첫 줄은 장기판 행의 수(N)와 열의 수(M)를 받는다

(1 ≤  N, M ≤ 1000).

둘째 줄은 말이 있는 위치의 행(R), 열(C)의 수와 졸이 있는 위치의 행(S), 열(K)의 수를 입력받는다.

단, 장기판의 제일 왼쪽 위의 위치가 (1,1)이다. 

각 행과 열은 R(1≤R≤N), C(1≤C≤M), S(1≤S≤N), K(1≤K≤M)이다. 

 

출력형식

말이 졸을 잡기 위한 최소 이동 횟수를 출력한다.

 

 

문제 유형

BFS

 

 

---

코드 

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

public class JO4189_장기2 {
	static int map[][];
	static boolean visited[][];
	static int n, m;
	static int r, c, s, k, res; 
	static Queue<Data> q;
	static class Data{
		int x;
		int y;
		int cnt;
		public Data(int x, int y, int cnt) {
			this.x = x;
			this.y = y;
			this.cnt = cnt;
		}
	}
	
	static int dx[] = {1, 2, 2, 1, -1, -2, -2, -1};
	static int dy[] = {-2, -1, 1, 2, 2, 1, -1, -2};
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		m = sc.nextInt();
		r = sc.nextInt(); // 말 행
		c = sc.nextInt(); // 말 열
		s = sc.nextInt(); // 졸 행
		k = sc.nextInt(); // 졸 열
		
		map = new int [n + 1][m + 1];
		visited = new boolean [n + 1][m + 1];
		q = new LinkedList<>();
		
		visited[r][c] = true;
		q.add(new Data(r, c, 0));
		go();
		System.out.println(res);
		
	}
	
	static void go() {
		Data cur = null;
		while(!q.isEmpty()) {
			cur = q.poll();
			if(cur.x == s && cur.y == k) {
				res = cur.cnt;
				return;
			}
			
			for (int dir = 0; dir < 8; dir++) {
				int nx = cur.x + dx[dir];
				int ny = cur.y + dy[dir];
				
				if(nx < 1 || ny < 1 || nx > n || ny > m )
					continue;
				
				if(visited[nx][ny])
					continue;
				
				visited[nx][ny] = true;
				q.add(new Data(nx, ny, cur.cnt + 1));
			}
		}
	}
}

 

처음에 답이 4가 나와서 당황했는데 알고보니 델타배열을 상하좌우 4가지밖에 안만들어서 그런거였다. 

그리고 (1,1)부터 시작하기 때문에 범위 설정을 좀 신경써야 한다.

문제를 꼼꼼하게 읽어야겠다고 다시금 생각했다.