PS/BOJ

백준 1331 나이트투어 / JAVA

얍연구소장 2023. 4. 19.

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

댓글