[Topcoder] MazeMaker(미로 제작자)

마이크 마제마이스터는 최근 그의 뒷마당에 큰 미로를 만들었다. 미로의 i번째 요소의 j번째 문자는 사각형이 통과할 수 없는 덤불이면 'X'이고, 그렇지 않으면 '.'이다. 마이크는 그의 친구인 점프 짐이 미로를 풀기를 원한다. Jim은 열 startCol의 행 startRow에서 시작합니다.

전형적인 미로 해결사들과는 달리, 짐은 단순히 걷는 것이 아니라 미로를 통해 점프할 수 있는 능력을 가지고 있습니다. 짐의 가능한 움직임은 moveRow와 moveCol에 설명되어 있다. i번째 요소는 짐이 현재 행을 moveRow[i]로 변경하고 현재 열을 moveCol[i]로 변경할 수 있는 이동에 해당합니다. 예를 들어 moveRow = {1, 0, -1}이고 moveCol = {3, -2, 5}인 경우 Jim의 합법적 이동은 (1, 3), (0, -2) 및 (-1, 5)입니다. 그러나 짐은 미로의 경계 밖으로 움직일 수 없고, 지나갈 수 없는 덤불 위에 착륙할 수도 없다.

마이크는 짐이 나갈 수 없게 미로를 만들고 싶어하고, 미로 안에 있는 '.'가 있는 어떤 감방에도 출구를 배치할 수 있다. 만약 이것이 불가능한 것으로 밝혀진다면, 마이크는 짐의 여행이 가능한 한 오래 걸리도록 만들고 싶어합니다. 짐은 영리하고, 그는 항상 그가 할 수 있는 최소한의 점프 횟수로 미로를 빠져나갈 것이다. 짐이 미로를 빠져나오기 위해 할 최대 점프 횟수를 반환합니다. 만약 그가 미로를 빠져나가는 것이 불가능하다면, 대신 -1을 반환합니다.

Definition

Class:

 

MazeMaker

Method:

 

longestPath

Parameters:

 

vector <string>, int, int, vector <int>, vector <int>

Returns:

 

int

Method signature:

 

int longestPath(vector <string> maze, int startRow, int startCol, vector <int> moveRow, vector <int> moveCol)

(be sure your method is public)

Examples

0)

{"...", "...", "..."}

0

1

{1,0,-1,0}

{0,1,0,-1}

Returns: 3

Here Jim can move up, down, left and right. Mike will set the exit in one of the bottom corners, which take Jim 3 steps to reach.

1)

{"...", "...", "..."}

0

1

{1, 0, -1, 0, 1, 1, -1, -1}

{0, 1, 0, -1, 1, -1, 1, -1}

Returns: 2

This is the same problem, but now Jim can move diagonally. With this, he can reach any section in at most two steps.

2)

{"X.X", "...", "XXX", "X.X"}

0

1

{1, 0, -1, 0}

{0, 1, 0, -1}

Returns: -1

Here Mike can place the exit in the empty section of the bottom row; Jim can never reach it.

3)

{".......", "X.X.X..", "XXX...X", "....X..", "X....X.", "......."}

5

0

{1, 0, -1, 0,-2, 1}

{0, -1, 0, 1, 3, 0}

Returns: 7

4)

{"......."}

0

0

{1, 0, 1, 0, 1, 0}

{0, 1, 0, 1, 0, 1}

Returns: 6

5)

{"..X.X.X.X.X.X."}

0

0

{2,0,-2,0}

{0,2,0,-2}

Returns: -1

---

#include <string>
#include <vector>
#include <queue>
using namespace std;

class MazeMaker{
public:
    int longestPath(vector <string> maze, int startRow, int startCol, vector <int> moveRow, vector <int> moveCol){
        int max = 0;
        int width = maze[0].size();
        int height = maze.size();
        int board[50][50]; 
        // constraint 상 moveRow 크기는 1~50

너비 우선 탐색으로 각 지점마다까지 소요되는 이동 횟수를 구하고 

 

가장 오래 걸리는 지점의 이동횟수를 반환하여 푼다. 

 

board 행렬은 각 지점마다 소요되는 이동횟수를 기록하기 위해 만들어주었다. 

 

        for(int i=0; i<height; i++){
            for(int j=0; j<width; j++){
                board[i][j] = -1;
                //이동횟수 기록을 위한 행렬
            }
        }

아직 한번도 방문하지 않은 지점은 -1로 처리해준다. 초기화를 위해 전체를 -1로 해준다. 

        board[startRow][startCol] = 0;
        queue<int> queueX;
        queue<int> queueY;
        queueX.push(startCol);
        queueY.push(startRow);

시작 지점은 이동횟수가 아직 0이므로 0으로 초기화해준다. 

 

그리고 너비 우선 탐색을 위해 X, Y 좌표별로 queue를 선언해주고, 초기 위치를 push한다. 

 

        while(queueX.size() > 0){
            int x = queueX.front(); 
            int y = queueY.front();
            queueX.pop(); queueY.pop();
            
            for(int i=0; i<moveRow.size(); i++){
            .
            .
            .
                } 
            }
        }

Queue가 바닥날때까지 Queue를 pop하고, 현재 x, y에서 이동한 결과를 너비 우선 탐색한다.

            for(int i=0; i<moveRow.size(); i++){
                int nextX = x + moveCol[i];
                int nextY = y + moveRow[i];
                if(nextX >= 0 && nextX < width && nextY >=0 && nextY < height && maze[nextY].substr(nextX,1) == "." && board[nextY][nextX] == -1)
                   {
                    board[nextY][nextX] = board[y][x] + 1;
                    queueX.push(nextX);
                    queueY.push(nextY);
                }

전체 이동 케이스마다 다음의 X, Y(NextX, NextY)를 구하고 이 좌표가 이동 가능한 경우일 때, 그리고 아직 이 지점이 

 

방문한 적 없는 지점이라면 이전 지점(x, y)에서의 이동횟수에서 1을 더해준다. 

 

이로써 각 지점마다 이동할 수 있는 최단 이동횟수가 구해진다.  

 

그리고 새로운 이동좌표를 queue에 push한다.

        for(int y=0; y<height; y++){
            for(int x=0; x<width; x++){
                if(maze[y].substr(x,1) == "." && board[y][x] == -1)
                    return -1;
                max = std::max(max, board[y][x]);
            }
        }
        
        return max;

너비 우선 탐색이 모두 끝났으면 전체 board를 순회하면서 가장 최대값(max)을 구하여 반환한다.

 

하지만 덤불이 아닌 지점(.)이면서 board가 -1인 경우는 이동이 아예 불가한 경우이므로 -1을 반환한다.