1600. 말이 되고픈 원숭이

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

1600번: 말이 되고픈 원숭이

 

 

(0,0)에서 시작해서 (W-1,H-1)에 도달하기까지 상하좌우 무빙(횟수 제한 없음) , 그리고 말의 무빙 K번을 사용해서 최소한의 무빙횟수를 구하는 문제이다. 단, 1값으로는 이동할 수 없다.

 

일반적인 BFS와 크게 다르지 않다.

솔루션의 핵심은 3차원 bool 벡터를 사용해서 check[ y 좌표 ] [ x 좌표 ] [ 말의 움직임 사용 횟수 (=hcnt] 을 만들어 주었다는 것이다.

check[y][x][0] - > (x,y) 좌표로 이동하는데 말의 움직임을 0번 사용했다는 뜻.

check[y][x][1] - > (x,y) 좌표로 이동하는데 말의 움직임을 1번 사용했다는 뜻.

 

소스코드를 보면서 자세히 설명하도록 하겠다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
#define FASTio ios_base :: sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define endl '\n' 

using namespace std;

int k,h,w;
vector < vector<int> > area(201, vector<int>(201));

bool check[201][201][31];
int dy[]={-1,1,0,0,-1,-2,-2,-1,1,2,2,1};
int dx[]={0,0,-1,1,-2,-1,1,2,-2,-1,1,2};

int bfs(int y,int x)
{   
    queue< pair< pair<int,int>,pair<int,int>>>q;
    
    // (y좌표,x좌표), (horse무빙 횟수, 총 무빙 횟수)
    q.push(make_pair(make_pair(y,x),make_pair(0,0)));
    check[y][x][0]=true;

    while(!q.empty())
    {
        int y = q.front().first.first;
        int x = q.front().first.second;
        int hcnt = q.front().second.first;
        int cnt = q.front().second.second;

        q.pop();

        if(y==h-1 && x==w-1)
        {
            return cnt;
        }

        for(int i=0;i<12;i++)
        {
            int ny = y + dy[i];
            int nx = x + dx[i];

            if(ny>=0 && nx>=0 && ny<h && nx<w && area[ny][nx]==0)
            {   

                // horse moving 사용
                if(hcnt<k && i>=4 && check[ny][nx][hcnt+1]==false)
                {   
                    check[ny][nx][hcnt+1] = true;
                    q.push(make_pair(make_pair(ny,nx),make_pair(hcnt+1,cnt+1)));
                }
                

                // monkey monving 사용
                if(i<4 && check[ny][nx][hcnt]==false)
                {
                    check[ny][nx][hcnt] = true;
                    q.push(make_pair(make_pair(ny,nx),make_pair(hcnt,cnt+1)));
                }
            }
        }

    }
    
	// 목적지에 도달하지 못한경우 
    return -1;
}

int main()
{
    FASTio;
    cin >> k >> w >> h;

    // Input
    for(int i=0;i<h;i++)
    {
        for(int j=0;j<w;j++)
        {
            cin >> area[i][j];
        }
    }

    int ans = bfs(0,0);
    cout << ans;

    return 0;
}

Solution

(0,0)에서 BFS를 시작해서 BFS를할때 큐에 총 네가지 요소를 인풋해주었다.

큐에는 (현재 y좌표, 현재 x좌표), (말의 움직임 사용횟수, 총 움직임 수) 를 저장하여 BFS를 진행하도록 하였는데, 

 

우선 영역내부에서 현재 말의 움직임 사용횟수가 main에서 입력한 k값보다 작고, 해당 좌표로 말의 움직임을 사용해서 가본 적이 없다면, 해당 좌표로 말의 움직임을 사용할 수 있다는 의미이므로 큐에 말의 움직임을 사용한 다음 좌표와 말의 움직임을 의미하는 hm+1, cnt+1을 푸쉬해준다. 

 

그리고 만약 원숭이의 움직임(상하좌우)을 사용하여 해당좌표에 가보지 않은 경우, 큐에 다음 좌표와 hm, cnt+1을 푸쉬해준다.

 

이렇게 BFS를 진행하다 목적지에 도달하면 총 움직임 횟수를 리턴.

만약 큐에 있는 원소가 모두 pop될 동안 목적지에 도달하지 못하였으면 -1을 리턴

 

 

 

 

말의 움직임을 저장한다는 아이디어만 있으면 쉽게 풀 수 있는 문제였다.

 

이 문제는 다음 문제와 같은 유형으로 현재상태에 대한 정보를 추가적으로 저장하면 쉽게 해결할 수 있다.

다음 문제들은 다음 포스팅에서 짧게 다루도록 하겠다.

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

2206번: 벽 부수고 이동하기

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

14442번: 벽 부수고 이동하기 2