백준 3055. 탈출

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

3055번: 탈출

 

홍수의 시작지점들과 고슴도치의 시작점을 큐에 넣고 bfs 를 진행하면 된다. 

처음에 저지른 실수가 고슴도치와 홍수를 각각 다른 큐에 넣은것인데 홍수와 고슴도치가 같이 한칸씩 이동되야 하므로 동일한 큐에 넣어서 관리해야 한다. 

또한 고슴도치는 물이 찰 예정인 칸은 이동할수 없으므로 같은 큐에 홍수의 시작지점들부터 넣고 그다음에 고슴도치의 시작지점을 넣어야 한다. 그래야만 현재 물이 있는 칸들이 모두 다음 칸으로 확산되고 그 후에 고슴도치가 이동할수 있는지 아닌지 판단 할 수 있다.

만약 고슴도치의 위치부터 큐에 넣으면 고슴도치가 물이 확산되는 위치에 존재하게 될 수도 있다. 

 

다음과 같은 구조체를 만들어 큐에 넣어줬다.

struct loc
{
    int type; // 0:홍수, 1:고슴도치
    int r;
    int c;
    int depth;
};