[백준 1600] - 말이 되고픈 원숭이(C++)[골드3]

 

문제

https://www.acmicpc.net/problem/1600

1600번: 말이 되고픈 원숭이

---

🔎문제 해석

원숭이의 동작수의 최소값을 구해야 하므로, BFS 알고리즘을 이용해서 출발지부터 도착지점까지 갈 수 있는지를 판단해야 합니다.

문제는 간단합니다.

queue를 이용해서 좌표와 말처럼 이동한 횟수를 계속해서 기록해 둡니다.

만약 말처럼 이동한 횟수가 k-1 이하라면 말처럼 이동할 수 있습니다.

하지만 k이상이라면 말처럼 이동할 수 없습니다.

 

즉 queue에서 기록한 이동 횟수를 비교해서 말처럼 이동 -> 원숭이처럼 이동한 좌표를 계속해서 queue에 넣어둡니다.

초기에는 queue에 좌표와 말이동 횟수, 이동 횟수를 모두 넣었더니 메모리초과가 발생했습니다.

따라서 queue에는 좌표와 말 이동 횟수만 넣기로 했고, 때로 배열을 하나 만들어서 이동 횟수를 계속해서 기록했습니다.

 

이동횟수를 기록하는 배열은 3차원 배열로 visit [h][w][k+1]로 선언해 줬습니다.

만약 말로 이동할 시  visit(기준좌표)[말이동 횟수]+ 1 = visit(이동좌표)[말 이동횟수 +1] 해줘야 합니다.

즉 이전 좌표에서 말 이동 횟수  + 1 한 값을 이동좌표와 말처럼 이동했기에 말 이동 횟수+1 한 배열에 넣어줬습니다.

 

말처럼 이동했다면

visit [newRow][newCol][horse+1] = visit [Row][Col][horse]+1

만약 원숭이처럼 이동했다면

visit [newRow][newCol][horse]= visit [Row][Col][horse]+1

 

그리고 만약 이동좌표가 이미 방문한 지역이라면 그 지역은 방문할 필요가 없기에 예외처리 해줬습니다.

모든 탐색을 마치고 나서 , 도착지점까지 가는데 이동한 횟수의 최솟값을 구해주면 됩니다.

여기서 도착지점에 대해서 말처럼 이동한 횟수에 대한 모든 경우의 수 중에서 최소값을 구해주면 됩니다.

for(int i=0; i <=k; i++){
    answer=min(answer, visit [w-1][h-1][i]);
}

 

 

💻전체 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <limits.h>
using namespace std;
vector<vector<int>> graph;
vector<vector<vector<int>>> v;
queue<pair<pair<int, int>, int>> q; // x,y 좌표 , 말 처럼 움직인 횟수.
int k, w, h = 0;
int hmove[8][2] = {{-2, -1}, {-2, 1}, {-1, -2}, {-1, 2}, {1, -2}, {1, 2}, {2, -1}, {2, 1}};
int Mmove[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 상하좌우
void funct();
int answer = INT_MAX;
int main()
{
    cin >> k;
    cin >> h >> w;
    graph.resize(w, vector<int>(h, 0));
    v.resize(w, vector<vector<int>>(h, vector<int>(k + 1, INT_MAX)));
    for (int i = 0; i < w; i++)
    {
        for (int j = 0; j < h; j++)
        {
            cin >> graph[i][j];
        }
    }
    funct();
    for (int i = 0; i <= k; i++)
    {
        answer = min(answer, v[w - 1][h - 1][i]);
    }
    if (answer == INT_MAX)
        cout << -1 << endl;
    else
        cout << answer << endl;
}
void funct()
{

    q.push(make_pair(make_pair(0, 0), 0));
    v[0][0][0] = 0;
    while (!q.empty())
    {
        auto loc = q.front().first; //(row, col)
        int lim = q.front().second; //말처럼 이동한 횟수
        q.pop();
        if (lim + 1 <= k)
        { // 만약 k번 움직였다면 말의 움직임은 할 수 없음.
            for (int i = 0; i < 8; i++)
            {
                int temprow = loc.first + hmove[i][0];
                int tempcol = loc.second + hmove[i][1];
                if (temprow < 0 || temprow >= w || tempcol < 0 || tempcol >= h || graph[temprow][tempcol] == 1)
                { // 적절한 이동이 아니라면(배열을 넘어가거나, 장애물을 밟을 경우)
                    continue;
                }
                if (v[temprow][tempcol][lim + 1] != INT_MAX) //처음 방문한것이 아니라면. 
                {
                    continue;
                }
                q.push(make_pair(make_pair(temprow, tempcol), lim + 1));
                v[temprow][tempcol][lim + 1] = v[loc.first][loc.second][lim] + 1; //이전 좌표 이동횟수 + 1
            }
        }
        for (int i = 0; i < 4; i++)
        {
            int temprow = loc.first + Mmove[i][0];
            int tempcol = loc.second + Mmove[i][1];
            if (temprow < 0 || temprow >= w || tempcol < 0 || tempcol >= h || graph[temprow][tempcol] == 1)
            { // 적절한 이동이 아니라면(배열을 넘어가거나, 장애물을 밟을 경우)
                continue;
            }
            if (v[temprow][tempcol][lim] != INT_MAX) //처음 방문이 아니라면.
            {
                continue;
            }
            q.push(make_pair(make_pair(temprow, tempcol), lim));
            v[temprow][tempcol][lim] = v[loc.first][loc.second][lim] + 1; //이전 좌표 이동횟수 +1
        }
    }
}

 

😀느낀 점

• 초기 풀이 방식에서는 배열을 추가로 만들기 싫어서 , queue 자료형에 다 집어넣었다.
  • 하지만 이러한 방식은 메모리를 상당히 많이 잡아먹는 것을 알게 되었고, 새로운 배열을 생성하는 것이 메모리 초과를 피하는 방법이라고 생각했다.
• 따라서 queue 자료형에 무식하게 집어넣지 말고, 배열로 이용할 수 있는 값들은 배열을 사용해야겠다.