개요

백준3055: 탈출

• 입력
  첫째 줄에 50보다 작거나 같은 자연수 R과 C가 주어진다.

  다음 R개 줄에는 티떱숲의 지도가 주어지며, 문제에서 설명한 문자만 주어진다. 'D'와 'S'는 하나씩만 주어진다.

• 출력
  첫째 줄에 고슴도치가 비버의 굴로 이동할 수 있는 가장 빠른 시간을 출력한다. 만약, 안전하게 비버의 굴로 이동할 수 없다면, "KAKTUS"를 출력한다.

접근 방식

1. [백준 3055번: 탈출] 문제와 아주 판박이인 문제다.
2. 차이점은 밖으로 탈출하는 것이 아닌, 비버의 굴인 D로 들어가야 하는 문제다.

코드

#include<iostream>
#include<queue>

using namespace std;
int height = 0, width = 0;
char TW[51][51];
queue<pair<int,int>> hedgehog;
bool visitedH[51][51];
queue<pair<int,int>> flood;
bool visitedF[51][51];

int dx[4] = { 0,0,-1,1 };
int dy[4] = { 1,-1,0,0 };

void BFS(int targetA, int targetB);

void input() {
	int targetA = 0, targetB = 0;
	cin >> height >> width;
	fill(&visitedH[0][0], &visitedH[50][50], false);
	fill(&visitedF[0][0], &visitedF[50][50], false);
	for (int i = 0; i < height; i++) {
		for (int j = 0; j < width; j++) {
			cin >> TW[i][j];
			//물 시작점이라면 flood큐에 넣어주기
			if (TW[i][j] == '*') {
				flood.push({ i,j });
				visitedH[i][j] = true;
			}
			//고슴도치 시작점 hedgehog큐에 푸시해주기
			else if (TW[i][j] == 'S') {
				hedgehog.push({ i,j });
				visitedF[i][j] = true;
					
			}
			//비버 굴이면 저장
			else if (TW[i][j] == 'D') {
				targetA = i;
				targetB = j;
			}
		}
	}
	BFS(targetA,targetB);
}

void BFS(int targetA,int targetB) {
	int level = 1;
	
	while (!hedgehog.empty()) {
		// 큐 사이즈는 가변적이므로 변수에 할당
		int hSize = hedgehog.size();
		int fSize = flood.size();
		//홍수 bfs 레벨 1 만큼만 진행
		for (int i = 0; i < fSize; i++) {
			pair<int,int> cur = flood.front();
			flood.pop();
			for (int j= 0; j < 4; j++) {
				int nextA = cur.first + dx[j];
				int nextB = cur.second + dy[j];
				//다음 좌표가 빈칸이면서, 시작 좌표가 아니라면 한칸씩 번지기
				if (nextA >= 0 && nextB >= 0 && nextA < height && nextB < width && TW[nextA][nextB] == '.'&& TW[nextA][nextB]!='S') {
					if (!visitedF[nextA][nextB]) {
						visitedF[nextA][nextB] = true;
						flood.push({ nextA,nextB });
					}
				}
			}
		}
		
		for (int i = 0; i < hSize; i++) {
			pair<int, int> cur = hedgehog.front();
			hedgehog.pop();

			for (int j = 0; j < 4; j++) {
				int nextA = cur.first + dx[j];
				int nextB = cur.second + dy[j];
				//목적지 'D'에 도달하면서 물이 침범 안햇다면 답 출력
				if (nextA ==targetA && nextB ==targetB && !visitedF[nextA][nextB]) {
					cout << level;
					return;
				}
				//다음칸이 범위 내에 존재하면서, 물이 침범 안하고, 빈칸이라면 
				if (nextA >= 0 && nextB >= 0 && nextA < height && nextB < width && !visitedF[nextA][nextB] && TW[nextA][nextB] == '.') {
					//방문 안 했다면
					if (!visitedH[nextA][nextB]) {
						//방문 체크
						visitedH[nextA][nextB] = true;
						//큐에 푸시
						hedgehog.push({ nextA,nextB });
					}
				}
			}
		}
		//레벨 증가
		level++;
	}
	//KAKTUS 출력
	cout << "KAKTUS";

}

int main() {
	input();
}

문풀후생

판박이