Red Knight's Shortest Path

출처 : 해커 랭크

난이도 : 중간

알고리즘 : BFS

 

일반 체스에서는 말이 검은색과 흰색, 두 가지 색으로만 구성됩니다. 하지만 저희 체스 버전에서는 독특한 움직임을 가진 새로운 말을 추가했습니다. 이 버전에서 가장 강력한 말 중 하나는 빨간색 나이트 입니다 .

아래 그림에서 볼 수 있듯이 붉은색 기사는 현재 위치를 기준으로 여섯 가지 다른 위치(상단 왼쪽, 상단 오른쪽, 오른쪽, 하단 오른쪽, 하단 왼쪽, 왼쪽)로 이동할 수 있습니다.

보드는 크기의 격자입니다 n x n 각 셀은 좌표 쌍으로 식별됩니다. (i,j), 어디 i행 번호이고 j는 열 번호이며 둘 다 0부터 인덱스됩니다. 따라서 (0, 0),왼쪽 상단 모서리입니다. (n - 1, n - 1)오른쪽 하단 모서리입니다.

printShortestPath그리드 크기를 입력으로 받는 함수를 완성하세요 .n, 그리고 시작 및 종료 위치의 좌표(i_start, j_start) 그리고 (i_end, j_end)각각을 입력으로 사용합니다. 이 함수는 아무것도 반환하지 않습니다.

빨간색 기사의 시작 위치 좌표와 목적지 좌표가 주어졌을 때, 빨간색 기사가 목적지에 도달하기 위해 이동해야 하는 최소 횟수를 출력하고, 그 후 목적지에 가장 짧은 시간 안에 도달하기 위해 따라야 하는 이동 순서를 출력하세요. 목적지에 도달할 수 없는 경우, "Impossible"이라는 단어만 출력하세요.

참고: 목적지까지 이어지는 최단 경로는 여러 개일 수 있습니다. 따라서 빨간색 기사가 가능한 이웃 위치를 다음과 같은 우선순위 순서로 고려한다고 가정합니다: UL, UR, R, LR, LL, L. 다시 말해, 가능한 옵션이 여러 개 있는 경우, 빨간색 기사는 최단 경로를 찾을 수 있는 한 이 목록에서 첫 번째 이동을 우선시합니다. 샘플 입력 확인2 예를 들어.

입력 형식

첫 번째 입력 줄에는 단일 정수가 포함됩니다.n두 번째 줄에는 공백으로 구분된 네 개의 정수가 포함됩니다. i_start, j_start, i_end, j_end. (i_start, j_start)시작 위치의 좌표를 나타냅니다. (i_end, j_end) 최종 위치의 좌표를 나타냅니다.

제약 조건

• 5 ≤ n ≤200
• 0 ≤ i_start, j_start, i_end, j_end < n
• 시작 위치와 종료 위치가 다릅니다

출력 형식

목적지에 도달할 수 있으면 두 줄을 출력합니다. 첫째 줄에는 빨간 기사가 목적지에 도달하기 위해 이동해야 하는 최소 횟수를 나타내는 정수 하나를 출력합니다. 둘째 줄에는 공백으로 구분하여 이동 순서를 출력합니다.

목적지에 도달할 수 없는 경우, 단어만 포함된 한 줄을 출력합니다 Impossible.

샘플 입력 0

7 
6 6 0 1

샘플 출력 0

4 
울 울 울 엘

설명 0

샘플 입력 1

6 
5 1 0 5

샘플 출력 1

불가능한

설명 1

샘플 입력 2

7 
0 3 4 3

샘플 출력 2

2 
LR LL

설명 2

 

----------------------------------------------------------------------------------------------------------------------------

 

문제 해독

체스게임에서 말의 이동 가능 방향이 주어졌을때 시작위치에서 목적지 까지 가는 최단 경로를 구하는 문제

 

문제접근

 

말이 움직일 수 있는 위치를 x,y로 구성하고 구성한 이동방향과 동일한 인덱스의 이동 경로 배열을 만들어 이동 할때마다 경로를 추가하여 목적지에 도달하였을때 해당 경로를 출력. 단 경로 도달 실패시 이동 불가 문구 출력

 

public static void printShortestPath(int n, int i_start, int j_start, int i_end, int j_end)
    {
    // Print the distance along with the sequence of moves.
        int[] dy = new int[] {-1, 1, 2, 1, -1, -2};
        int[] dx = new int[] {-2, -2, 0, 2, 2, 0};
        string[] droad = new string[] {"UL", "UR", "R", "LR", "LL", "L"};
        
        bool[,] visited = new bool[n,n]; 
        Queue<(int x, int y, List<string> step)> q = new Queue<(int x, int y, List<string> step)>();
        q.Enqueue((i_start, j_start, new List<string>()));
        visited[i_start, j_start] = true;
        
        while(q.Count() > 0)
        {
            var (x, y, step) = q.Dequeue();
            
            if(x == i_end && y == j_end)
            {
                Console.WriteLine($"{step.Count()}");
                foreach(string s in step)
                {
                    Console.Write($"{s} ");
                }
                return;
            }
            for(int i = 0; i < 6; i++)
            {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if(nx < 0 || nx >= n || ny < 0 || ny >= n)
                    continue;
                if(visited[nx,ny])
                    continue;
                
                visited[nx,ny] = true;

                List<string> newStep = new List<string>(step);
                newStep.Add(droad[i]);
                q.Enqueue((nx, ny, newStep));
            }
        }
        
        Console.Write("Impossible");
    }