[구현] 백준 1331번 나이트 투어 - JAVA

 

 

오늘은 오랜만에 백준 문제를 풀었다.

나이트 투어는 문제 자체는 쉬운데...

독해에서 난항을 겪었다 ㅋㅋㅋ

 

기술 블로그에 쓰신 분도 별로 없길래 남기고자 한다.

 

---

1. 출처

---

 

 

1331번: 나이트 투어

 

 

 

 

---

2. 설계

---

 

 

1) 체스에서 나이트는 어떻게 움직일까?

사실 나는 체스는 둬본 적도 없고, 관련 문제는 N-QUEEN 밖에 안풀어봐서 나이트가 어떻게 움직이는지 몰랐다.

근데 문제에도 제시가 안되어있어서 당황스러웠다.

 

 

 

체스 나이트는 현 위치에서

(+2, -1) (+2, 1)

(-2, -1) (-2, +1)

(+1, -2) (-1, +2)

(+1, +2) (-1, +2)

총 8방향으로 움직일 수 있다.

 

 

2) 체스판에서 나이트가 모든 칸을 정확히 한 번씩 방문해야 한다.

6x6 체스판의 위치 중 어디 먼저 방문할지 순차적으로 주어진다.

모든 칸에 1번 씩만 방문할 수 있으므로 중복 방문의 경우 바로 Invalid를 띄워주면 된다.

for(int i=1;i<=36;i++){
	String cmd = br.readLine();
	int row = cmd.charAt(1)-'0'-1;
	int col = cmd.charAt(0)-'A';

	if(map[row][col]!=0){
		result = "Invalid";
		break;
	}
    
	map[row][col] = i;
}

 

나는 1~36의 i를 가진 for을 돌면서 map에 저장해줬다. 그 중 0인 곳은 빈 곳이기 때문에 0이 아닌 곳에 또 넣으려고 하면 중복 방문이라고 체크했다.

 

 

3) 마지막으로 방문하는 칸에서 시작점으로 돌아올 수 있는 경로?

나는 처음의 이 의미가 36지점 즉 마지막 지점에서 1지점, 처음 지점으로 돌아올 수 있는가?를 묻는줄 알았다.

즉... 36 > 35 > 34 > ... > 1이 가능한가?를 묻는 줄 알았다.

 

근데 아니었다 ㅋㅋㅋㅋ 1~36까지 갔다가 다시 36에서 1번을 바로 올 수 있냐는 말이었다... 왜케 해석이 어려운거지?..

경로는 체스판에서 나이트가 움직이는 8방향으로만 이동했을 때 갈 수 있는 경로이다.

 

for(int i=1;i<=36;i++){
	String cmd = br.readLine();
	int row = cmd.charAt(1)-'0'-1;
	int col = cmd.charAt(0)-'A';

	if(map[row][col]!=0){
		result = "Invalid";
		break;
	}
    
	map[row][col] = i;
    
	if(i==1){
		firstLocation[0][0] = row;
		firstLocation[0][1] = col;
	}
}

 

그래서 2번 코드에서 가장 아래 i==1일 때, 즉 1번 경로를 미리 저장해둔 것이다.

 

if(result.equals("Valid")){
	move(firstLocation[0][0], firstLocation[0][1], 1);
}

 

모든 칸에 단 1번씩 36번을 방문했다면, move 함수로 이동해 1~36 > 1로 연결될 수 있는지 확인했다.

 

public static void move(int row, int col, int num){

	for(int d=0;d<8;d++){
		int nextR = row+drc[d][0];
		int nextC = col+drc[d][1];

		if(nextR<0 || nextR>=6 || nextC<0 || nextC>=6) continue;

		if(num==36 && map[nextR][nextC]==1) return;
            

		else if(map[nextR][nextC]==num+1) {
			move(nextR, nextC, num+1);
			return;
		}
	}

	result = "Invalid";
        
}

 

유사 DFS처럼 나이트가 가는 8방향에 현재의 다음 수가 존재한다면 다시 시스템 스택에 들어가게 했다.

주의점은 36이 나온 경우 다음에는 1이 연결되는지 확인해야한다.

 

 

---

3. 전체 코드

---

 

import java.io.*;

class Main {

    static int[][] map;
    static int[][] drc = {{2,-1},{2,1},{-2,-1},{-2,1},{1,-2},{-1,-2},{1,2},{-1,2}};
    static String result = "Valid";
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        map = new int[6][6];
        int[][] firstLocation = new int[1][2];
        
        for(int i=1;i<=36;i++){
            String cmd = br.readLine();
            int row = cmd.charAt(1)-'0'-1;
            int col = cmd.charAt(0)-'A';

            if(map[row][col]!=0){
                result = "Invalid";
                break;
            }
            map[row][col] = i;

            //1번 위치 저장
            if(i==1){
                firstLocation[0][0] = row;
                firstLocation[0][1] = col;
            }
        }

        if(result.equals("Valid")){
            move(firstLocation[0][0], firstLocation[0][1], 1);
        }

        System.out.println(result);
        
    }

    public static void move(int row, int col, int num){

        for(int d=0;d<8;d++){
            int nextR = row+drc[d][0];
            int nextC = col+drc[d][1];

            if(nextR<0 || nextR>=6 || nextC<0 || nextC>=6) continue;

            if(num==36 && map[nextR][nextC]==1) return;
            

            else if(map[nextR][nextC]==num+1) {
                move(nextR, nextC, num+1);
                return;
            }
        }

        result = "Invalid";
        
    }
}