백준 11451 - 팩맨

1. 문제 정리
  - 팩맨 두개가 존재한다.

  - 팩맨은 동서남북 4개의 방향으로 움직일 수 있다.

  - 하나의 팩맨을 움직이면 다른 팩맨 또한 같은 방향으로 움직인다.

  - 벽('X')이 존재하는 칸으로 가려하면 해당 팩맨은 움직이지 않는다.

  - 유령('G')이 존재하는 칸으로는 이동할 수 없다.

  - 팩맨이 화면 밖으로 나가면 반대에서 나타난다.

  - 두개의 팩맨의 좌표를 갖게 할 수 있을 때, 해당 지점까지 이동 방향의 문자열과 이동 횟수를 출력한다.

2. 접근
  - BFS로 풀 수 있는 문제라 생각하였다.

  - 하나의 팩맨을 기준으로 움직일 때 다른 팩맨의 움직임도 계산을 해주었다.

  - 방문 기록을 위한 4차원 배열을 만들었다.

 
3. 풀이

//2021.12.21
#include<iostream>
#include<vector>
#include<queue>
#include<set>
using namespace std;

struct pack{
    int x, y;
    string ans = "";
}typedef pack;

int n, m;
char a[50][50];
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
char d[] = {'N', 'S', 'W', 'E'};
int check[50][50][50][50] = {0, };
vector<pack> p;

void bfs(){
    queue<pair<pack, pack> > q;
    q.push({p[0], p[1]});
    while(!q.empty()){
        pack node1 = q.front().first;
        pack node2 = q.front().second;
        q.pop();
        if(node1.x == node2.x && node1.y == node2.y) {
            cout << check[node1.x][node1.y][node2.x][node2.y]-1 << ' ' << node1.ans << '\n';
            return;
        }
        for(int i = 0; i < 4; i++){
            pack next1 = {node1.x+dx[i], node1.y+dy[i], node1.ans+d[i]};
            pack next2 = {node2.x+dx[i], node2.y+dy[i], node2.ans+d[i]};
            if(next1.x < 0) next1.x = n-1;
            else if(next1.x >= n) next1.x = 0;
            if(next1.y < 0) next1.y = m-1;
            else if(next1.y >= m) next1.y = 0;
            if(next2.x < 0) next2.x = n-1;
            else if(next2.x >= n) next2.x = 0;
            if(next2.y < 0) next2.y = m-1;
            else if(next2.y >= m) next2.y = 0;
            if(a[next1.x][next1.y] == 'G' || a[next2.x][next2.y] == 'G') continue;
            if(a[next1.x][next1.y] == 'X'){
                next1.x = node1.x; next1.y = node1.y;
            }
            if(a[next2.x][next2.y] == 'X'){
                next2.x = node2.x; next2.y = node2.y;
            }
            if(check[next1.x][next1.y][next2.x][next2.y] > check[node1.x][node1.y][node2.x][node2.y]+1){
                check[next1.x][next1.y][next2.x][next2.y] = check[node1.x][node1.y][node2.x][node2.y]+1;
                q.push({next1, next2});
            }
        }
    }
    cout << "IMPOSSIBLE" << '\n';
    return;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t;
    cin >> t;

    for(int i = 0; i < t; i++){
        cin >> n >> m;
        for(int j = 0; j < n; j++){
            for(int k = 0; k < m; k++){
                cin >> a[j][k];
                if(a[j][k] == 'P'){
                    a[j][k] = '.';
                    p.push_back({j, k, ""});
                }
            }
        }
        for(int j = 0; j < n; j++){
            for(int k = 0; k < m; k++){
                for(int s = 0; s < n; s++){
                    for(int l = 0; l < m; l++){
                        check[j][k][s][l] = 2100000000;
                    }
                }
            }
        }
        check[p[0].x][p[0].y][p[1].x][p[1].y] = 1;
        bfs();
        p.clear();
    }

}

  - int dx[], dy[] : 각 x 방향, y 방향으로의 이동을 위한 배열이다.

  - char d[] : 이동한 방향에 따른 경로 저장의 편의를 위한 배열이다.

  - int check[][][][] : 순서대로 x1, y1, x2, y2를 이용하여  방문한 좌표인지 확인하고, 해당 좌표까지 최소 이동 횟수를 저장한다.

  - void bfs() : bfs를 수행하며, 팩맨의 좌표를 의미하는 node1, node2의 각 x, y 좌표가 일치할 경우에는 node1에 저장된 경로 문자열, check[node1.x][node1.y][node2.x][node2.y] 값을 출력하고, 그러지 않고 더 이상 bfs를 수행하지 못할 경우에는 "IMPOSSIBLE"을 출력하고 반환한다

    -> for문을 이용하여 dx, dy 배열을 활용해 각 팩맨의 위치를 변환한다. 그 중에 팩맨의 변환된 위치에 유령이 존재할 경우는 해당 과정을 뛰어넘고(continue), 벽이 존재하거나 화면 밖으로 나갈 경우 좌표를 재지정해준다. 그리고 해당 좌표의 check 배열을 검사하여 방문한 적이 없거나, 방문하기까지의 이동 횟수가 더 적을 경우 방문한 것으로 간주하여 queue에 팩맨의 좌표를 저장하고 check 배열의 값을 변화시킨다.
 
4. 소감

  오랜만에 푸는 bfs문제였다. 사실 완전탐색을 찾아보다가 풀게 된 문제인데, 표시된 난이도에 비해 그렇게 어렵게 느껴지지 않고 한번에 풀이 방법이 생각나고 그렇게 적용할 수 있었던 것에 대해 실력이 늘었구나라는 생각과 문제 풀이의 재미도 더 느낄 수 있었다.