[백준 16954] 움직이는 미로 탈출

문제: https://www.acmicpc.net/problem/16954

1)문제분류

-시뮬레이션

-BFS

2)문제해결

 -1초마다 벽을 이동시켜야 하기 때문에 1초마다 갈 수있는 위치를 큐에 담고, 벽을 이동시킨 후, 담아 놨던 큐로 탐색하며 또 이동..

 - 다만 문제에서 잘 읽어야 하는 부분은 "현재 위치에 서 있을 수도 있다" 와 

   "벽이 캐릭터가 있는 칸으로 이동하면 더 이상 캐릭터는 이동할 수 없다." 인 것 같다. 그에 따른 조건 처리를 잘 해줘야 할 듯 싶다.

-그리고 구현상 실수할 법한 부분은 벽이 이동할때 행이 큰 것부터 이동 시켜줘야 중복되서 값을 바꾸지 않는다.

(예로,연속으로 같은 행에 벽이있다고 치자. 행이 작은 것부터 바꿔서 '#'으로 만들었는데, 행이 큰것의 벽을 이동할때 이전의 바꾼  '#'을  '.'로 바꿔버리게 된다. 뭐 구현..방법의 차이가 있겠지만 내 구현방식으로는 실수할법한 부분 이었다)

#include<iostream>

#include<queue>

#include<algorithm>

#include<cstring>

using namespace std;

char map[10][10];

typedef struct Data

{

int x, y;

}Data;

Data wall[100];

int wcnt = 0;

int xrr[8] = {-1,-1,-1,0,0,1,1,1};

int yrr[8] = { -1,0,1,-1,1,-1,0,1 };

int chk[10][10];

int bfs()

{

chk[7][0] = 1;

queue<Data>pq;

pq.push({ 7,0 });

while (1)

{

int Size = pq.size();

int ok = 0;

memset(chk, false, sizeof(chk));

while (Size--)  //캐릭터가 갈 수 있는 위치 탐색

{

Data output = pq.front();

pq.pop();

if (map[output.x][output.y] == '#')continue; //벽이 캐릭터가 있는 칸으로 이동하면 더 이상 캐릭터는 이동할 수 없다

if (output.x == 0 && output.y == 7)

{

return 1;

}

for (int i = 0; i < 8; i++)

{

int cx = output.x + xrr[i];

int cy = output.y + yrr[i];

  if (cx < 0 || cy < 0 || cx>7 || cy>7 || chk[cx][cy] == true || map[cx][cy] == '#')continue;

chk[cx][cy] = true;

if (map[cx][cy] == '.')

{

pq.push({ cx,cy });

}

}

pq.push({ output.x,output.y });

ok = 1;

}

if (ok == 0)return 0;

for (int i = 0; i < wcnt; i++)  //벽 한칸씩 이동 

{

map[wall[i].x][wall[i].y] = '.';

if (wall[i].x + 1 < 8)

{

wall[i].x += 1;

map[wall[i].x][wall[i].y] = '#';

}

}

}

}

int cmp(Data a, Data b)

{

if (a.x == b.x)return a.x < b.x;

else

return a.x > b.x;

}

int main()

{

for (int i = 0; i < 8; i++)

{

for (int j = 0; j < 8; j++)

{

cin >> map[i][j];

if (map[i][j] == '#')

{

wall[wcnt].x = i;

wall[wcnt].y = j;

wcnt++;

}

}

}

sort(wall, wall + wcnt, cmp);

cout << bfs() << endl;

}