[BOJ][백준]BFS-18170 두 동전 언리미티드

 

 

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

18170번: 두 동전 언리미티드

문제

N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고, 두 동전의 위치는 다르다.

버튼은 "왼쪽", "오른쪽", "위", "아래"와 같이 4가지가 있다. 버튼을 누르면 두 동전이 버튼에 쓰여 있는 방향으로 동시에 이동하게 된다.

• 동전이 이동하려는 칸이 벽이면, 동전은 이동하지 않는다.
• 동전이 이동하려는 방향에 칸이 없으면 동전은 보드 바깥으로 떨어진다.
• 그 외의 경우에는 이동하려는 방향으로 한 칸 이동한다.이동하려는 칸에 동전이 있는 경우에도 한 칸 이동한다.

두 동전 중 하나만 보드에서 떨어뜨리기 위해 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 20)

둘째 줄부터 N개의 줄에는 보드의 상태가 주어진다.

• o: 동전
• .: 빈 칸
• #: 벽

동전의 개수는 항상 2개이다.

출력

첫째 줄에 두 동전 중 하나만 보드에서 떨어뜨리기 위해 눌러야 하는 버튼의 최소 횟수를 출력한다. 만약, 두 동전을 떨어뜨릴 수 없다면 -1을 출력한다.

 

******************************************************************************************************************

 

BFS 기본예제가 새로운 문제로 추가되었습니다. 문제가 독특합니다. 한번의 이동에 동전2개가 같이 움직이는 것 과,

종료조건이 두개의 동전 중 한개의 동전만을 떨어뜨려야 한다는 점이 기존의 문제와의 차별점이 되는데,

문제에서 주문한만큼 그대로 구현하면 됩니다. 두개의 동전을 한꺼번에 움직이는 만큼 queue에 넣어줘야할

인자가 두배로 늘어나는 점에 유의하고, 동전을 이동시킬때, 두개의 동전 중 한개의 동전이 벽에 부딪힌다고

움직이지 못하는 것이 아니라, 벽에 부딪히는 동전은 그대로 두고,

다른 동전을 이동시킬 수 있음에 유의하며 코딩을 하면 됩니다.

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int goY[4]={0,0,1,-1},goX[4]={1,-1,0,0};
int N,M;
char board[21][21];

struct POINT
{
    int y1,x1,y2,x2;
};

bool is_in_board(int y,int x)
{
    if(y<1||y>N||x<1||x>M)return false;
    return true;
}

int BFS(POINT start)
{
    queue<POINT>q;
    int visited[21][21][21][21];
    visited[start.y1][start.x1][start.y2][start.x2]=1;
    q.push(start);
    while(!q.empty())
    {
        POINT now=q.front();
        q.pop();
        for(int i=0;i<4;i++)
        {
            POINT next={now.y1+goY[i],now.x1+goX[i],now.y2+goY[i],now.x2+goX[i]};
            
            if(board[next.y1][next.x1]=='#')next.y1=now.y1,next.x1=now.x1;
            if(board[next.y2][next.x2]=='#')next.y2=now.y2,next.x2=now.x2;
            
            if(!is_in_board(next.y1,next.x1)&&!is_in_board(next.y2,next.x2)) continue;
            if(visited[next.y1][next.x1][next.y2][next.x2]) continue;
            //exit
            if(is_in_board(next.y1,next.x1)+is_in_board(next.y2,next.x2)==1)
                return visited[now.y1][now.x1][now.y2][now.x2];
            
            visited[next.y1][next.x1][next.y2][next.x2]=visited[now.y1][now.x1][now.y2][now.x2]+1;
            q.push(next);

        }
    }
    return -1;

}

int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cin>>N>>M;
    bool first=true;
    pair<int,int>x,y;
    for(int i=1;i<=N;i++)
        for(int j=1;j<=M;j++)
        {
            cin>>board[i][j];
            if(board[i][j]=='o')
            {
                if(first){first=false,x={i,j};}
                else y={i,j};
            }
        }
    cout<<BFS({x.first,x.second,y.first,y.second});
}

 

뜬금없이 왜 BFS문제가 추가되었는지 몰랐는데, 삼성 역테유형이랑 비슷해보여서 연습용으로 만드신게 아닌가..

생각해봅니다. 물론 역테기출보다는 구현량이 짧은데, 그런문제들의 기본 토대가 되기에 좋은 문제인 것 같습니다.