https://www.acmicpc.net/problem/1331
1331번: 나이트 투어
나이트 투어는 체스판에서 나이트가 모든 칸을 정확히 한 번씩 방문하며, 마지막으로 방문하는 칸에서 시작점으로 돌아올 수 있는 경로이다. 다음 그림은 나이트 투어의 한 예이다. 영식이는 6×
www.acmicpc.net
> 풀이
import java.util.Scanner;
/*
* 백준 1331 나이트투어
* #실버5
*/
public class boj_1331 {
static boolean[][] arr;
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
arr = new boolean[7][7];
String start = sc.nextLine();
int start_x = coordinate(start, 'x');
int start_y = coordinate(start, 'y');
System.out.println("start_x : " +start_x);
System.out.println("start_y : " +start_y);
int x = start_x;
int y = start_y;
for(int i = 1; i < 36; i++) {
String next = sc.nextLine();
int nx = coordinate(next, 'x');
int ny = coordinate(next, 'y');
chk(nx,ny,x,y);
x = nx;
y = ny;
}
// 마지막 위치에서 맨 처음으로 돌아올 수 있는지 검증
if(!knightLen(start_x, start_y, x, y)) {
Invalid();
}
System.out.println("Valid");
}
// x, y 좌표 구하는 함수
public static int coordinate(String s, char p) {
int x = s.charAt(0);
int y = s.charAt(1);
return p == 'x' ? x - 'A'+1 : y - '0';
}
// 다음 칸 이동 가능 여부 검증
public static void chk(int nx, int ny, int x, int y) {
if(arr[nx][ny] || !knightLen(nx,ny,x,y)) {
Invalid();
} else {
arr[nx][ny] = true;
}
}
// 나이트 이동가능 여부 검증
public static boolean knightLen(int nx, int ny, int x, int y) {
int len_x = Math.abs(nx-x);
int len_y = Math.abs(ny-y);
if((len_x == 2 && len_y == 1) || (len_x == 1 && len_y == 2)) {
return true;
}
return false;
}
// 이동불가 시 프로그램 종료함
public static void Invalid() {
System.out.println("Invalid");
System.exit(0);
}
}
'PS > BOJ' 카테고리의 다른 글
백준 1343 폴리오미노 (0) | 2023.04.20 |
---|---|
백준 5585 거스름돈 / JAVA (0) | 2023.04.19 |
백준 9465 스티커 / JAVA (0) | 2023.04.17 |
백준 1251 단어 나누기 / JAVA (0) | 2023.04.14 |
백준 5341 Pyramids / JAVA (1) | 2023.04.12 |
댓글