BOJ 6316

02 Apr 2020 • ProblemSolving

Pushing Boxes

문제출처

문제 해석

  • 박스를 특정 지점까지 최소로 움직이면서 갈 수 있는 경우를 구하는 문제입니다.
  • 2차원 배열에 S(사람),B(박스),T(목표지점)이 1개씩 주어집니다.
  • 사람이 이동하는 경로는 “eswn”으로 표현하고, 박스를 미는 경로는 “ESWN”으로 표현합니다.
  • 박스를 미는 횟수를 최소화하되, 만약 그러한 경우가 여러가지면 박스를 미는 횟수와 사람이 이동한 횟수의 합이 최소가 되는 경로를 구합니다.
  • 만약 위의 조건을 만족하는 경로가 여러가지면, 그 중 한 경로를 출력합니다.

설계(10)

  • 박스와 사람이 이동하는 상태에 따라 방문표시를 해주면서 탐색하는 bfs알고리즘 활용 문제입니다.
  • 우선, 박스와 사람의 상태에 따른 방문표시를 위해 4차원 배열을 사용합니다.
  • 사람이 박스를 미는 경우와 아닌 경우로 나뉩니다.
  • 사람의 다음 좌표와 박스의 좌표가 같으면 박스를 밀게 됩니다.
  • 그렇지 않은 경우 사람만 이동시키고 방문표시를 해줍니다.
  • 여기서, 박스를 미는 경우를 최소화해야 하기 때문에 priority queue를 사용합니다.

구현(40)

코드
#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>

#define MAXN 21
using namespace std;
char map[MAXN][MAXN];
bool visited[MAXN][MAXN][MAXN][MAXN];
int N,M;
int tx,ty,sx,sy,bx,by;
int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};
struct node{
    int x1,y1,x2,y2;
    int cnt1,cnt2;
    string path;
    bool operator < (const node& a) const{
        if (a.cnt2 == cnt2) return a.cnt1+a.cnt2 < cnt1+cnt2;
        return a.cnt2 < cnt2;
    }
};
priority_queue<node> q;
string dirs = "eswnESWN";
bool is_range(int x, int y){
    return (x>=0 && y >= 0 && x < N && y <M);
}
string bfs(){
    q.push({sx,sy,bx,by,0,0,""});
    visited[sx][sy][bx][by] = true;
    while(!q.empty()){

        int x1 = q.top().x1;
        int y1 = q.top().y1;
        int x2 = q.top().x2;
        int y2 = q.top().y2;
        string cur_path = q.top().path;
        int cnt1 = q.top().cnt1;
        int cnt2 = q.top().cnt2;
        if (x2 == tx && y2 == ty) {
            return cur_path;
        }
        q.pop();
        for (int k =0 ;k<4; k++){
            int nx1 = x1 + dx[k];
            int ny1 = y1 + dy[k];
            if (!is_range(nx1,ny1) || map[nx1][ny1]=='#') continue;
            // 박스를 미는 경우
            if (nx1 == x2 && ny1 == y2){
                int nx2 = x2 + dx[k];
                int ny2 = y2 + dy[k];
                if (!is_range(nx2,ny2)) continue;
                if (map[nx2][ny2]=='#' || visited[nx1][ny1][nx2][ny2]) continue;
                visited[nx1][ny1][nx2][ny2] = true;
                q.push({nx1,ny1,nx2,ny2,cnt1,cnt2+1,cur_path+dirs[k+4]});
            }
            // 박스를 찾는 경우
            else{
                if(visited[nx1][ny1][x2][y2]) continue;
                visited[nx1][ny1][x2][y2] = true;
                q.push({nx1,ny1,x2,y2,cnt1+1,cnt2,cur_path+dirs[k]});
            }
        }
    }
    return "Impossible.";
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 0;
    while (1){
        cin >> N >> M;
        if (N ==0  && M == 0) break;
        memset(visited,false,sizeof(visited));
        while (!q.empty()) q.pop();

        for (int i =0;i<N; i++){
            cin >> map[i];
            for (int j =0;j<M;j++){
                if (map[i][j] == 'S') {
                    sx=i,sy=j;
                    map[i][j] = '.';
                }
                else if (map[i][j] == 'B'){
                    bx = i, by = j;
                    map[i][j] = '.';
                }
                else if (map[i][j] == 'T'){
                    tx = i , ty = j;
                    map[i][j] = '.';
                }
            }
        }
        cout <<"Maze #"<< ++t <<"\n";
        cout << bfs() <<"\n\n";
    }
    return 0;
}
디버깅
  • 처음에 박스를 미는 횟수를 최소화해야 한다는 조건을 보지 못해서 queue를 사용하였습니다. priority queue로 변경하였습니다.
  • 박스를 미는경우와 찾는 경우의 조건을 판별하기 전에 일단 사람이 벽을 통과하면 안되므로 map[nx][ny]==’#’인지 체크를 해주었어야하는데, 사람이 이동하는 경우에서만 판별을 해주는 실수를 하였습니다.
제출결과
  • 100ms

마무리

  • 구슬탈출 문제와 비슷한 유형의 bfs문제였습니다. 실수한 부분을 찾는데 시간이 오래걸렸습니다.
 BOJ

Related Posts