백준 3055번 : 탈출 _ C++

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

3055번: 탈출

 

#그래프 #BFS알고리즘 #gold4

 

회고

 

✔ 큐 두개

처음엔 큐 한개로 물과 고슴도치의 이동을 처리했는데 그렇게 하자니 물 좌표를 넣고 고슴도치 좌표를 이동시켜야 하는데 물 좌표만 계속 업데이트 되는 현상이 발생해서 물 큐와 고슴도치 큐 두개로 나눠서 풀어줬다.

 

✔  고뇌의 연속..

홈페이지에 나와있던 예제들은 전부 통과하였는데 채점 결과는 계속 '틀렸습니다' 만 출력되어 정말 멘붕이었다.

 

https://www.acmicpc.net/board/view/27210 

글 읽기 - 3055번 탈출 대회 Test Case 올려봅니다.

 

해당 페이지에 테스트 케이스를 친절하신 분이 올려주셔서 돌려봤는데 아니나 다를까 여러개의 테케가 다른 답이 나왔었다.

2-3시간동안 머리를 싸매며 고슴도치가 지나간 좌표를 visit 배열을 통해 카운팅 해 주어 저장된 값을 출력하거나, 비버 둥지 인접 타일의 제일 작은 숫자를 출력해보는 등 이상한 헛짓거리를 계속 하다가 .. 

 

큐를 한번 진행 할 때마다 횟수를 카운팅 해 주는 방식으로 변경하게 되었고 계속해서 틀리던 테케 중 일부가 드디어 맞게 되었다.

 

나머지 테케를 통과하지 못했는데 해당 원인은 비버의 둥지를 만나게되었을 때 반복문에서 빠져나오지 않아서 카운팅 횟수가 계속 올라가서 그런것이었다.. 원인을 찾기위해 한시간은 고민했는데 너무 어이없었다 ㅠ 그러나 PS는 항상 그런것..

정말 어이없었던 점은 마지막 한개 테케를 통과하지 못해서 그냥 채점할 때 몇퍼센트까지 올라가나 확인하려고 제출하였는데 '맞았습니다' 가 떠서 너무 당황했다 ㅋㅋ 그 테케가 잘못된 테케였나보다. (알고보니까 다른 분이 해당 테케가 이상하다고 댓글로 적어주셨던걸 이 글을 작성하면서 알게되었다)

 

코드

// '.' 빈 공간, '*' 물, 'X' 돌, 'D' 비버, 'S' 고슴도치
// '*'->'X' 불가능, '*'->'D' 불가능, 'S'->'X' 불가능, 'S'->'*' 불가능
// '*' 예정인 칸 'S' 불가능 => '*' 먼저 덮어씌우기
//BFS , 최소시간

#include <iostream>
#include <queue>
#include <iomanip>
#define MAX 51
using namespace std;

int r, c;
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };
queue<pair<int, int>>q;
queue<pair<int, int>> wq;
char map[MAX][MAX];
bool flag = false;
int cnt = 0;
int dX, dY;

bool isMap(int x, int y) {
	if ((0 <= x && x < r) && (0 <= y && y < c)) return true;
	else return false;
}


void bfs() {
	while (!q.empty()) {
		int wSize = wq.size();
		for (int i = 0; i < wSize; i++) { //물
			int wx = wq.front().first;
			int wy = wq.front().second;
			wq.pop();

			for (int i = 0; i < 4; i++) { 
				int twx = wx + dx[i];
				int twy = wy + dy[i];

				if (isMap(twx, twy) == 1 && map[twx][twy] == '.') {
					map[twx][twy] = '*';
					wq.push({ twx,twy });
				}
			}
		}


		int hSize = q.size();
		for (int i = 0; i < hSize; i++) { //고슴도치
			int x = q.front().first;
			int y = q.front().second;
			q.pop();

			for (int i = 0; i < 4; i++) {
				int tx = x + dx[i];
				int ty = y + dy[i];
				if (tx == dX && ty == dY) { //여기서 return 안했어서 틀렸음 ㅡㅡ
					flag = true;
					return;
				}
				if (isMap(tx, ty) == 1 && map[tx][ty] == '.') {
					map[tx][ty] = 'S';
					q.push({ tx,ty });
				}
			}
		}
		cnt++;
	}
}

int main() {
	cin >> r >> c;
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			cin >> map[i][j];
			if (map[i][j] == '*') {
				wq.push({ i,j });
			}
			if (map[i][j] == 'S') {
				q.push({ i,j });
			}
			if (map[i][j] == 'D') {
				dX = i;
				dY = j;
			}
		}
	}
	bfs();
	if (flag) cout << cnt+1;
	else cout << "KAKTUS";

	return 0;
}