백준 3055번 탈출

< 백준 3055번 탈출 - 마포 코딩박 >

사용한 알고리즘: BFS


 비어있는곳( . ) , 물( * ), 돌( X ), 굴( D ), 현재위치( S ) 로 구성된 grid를 주어집니다. 물이 인접한 칸으로 매분 이동할때,  현재위치에서 굴로 갈 수 있는지 묻는 문제였습니다.

문제풀이는 다음과 같습니다.

(1) (코드: 배열 Forest)
 초기 물이 있는 곳은 0분에 물이 차있다 생각하고 0으로 저장, 돌은 물이 퍼질 수 없으니 Infimum값으로 저장, 굴이 있는 위치는 기억하기 위해 -1 로 저장합니다.

(2) (코드: 18~29)
 물이 있는 지점이 0분에 물이 찬다고 생각하고, 이동 가능한 인접 칸들을 탐색하며 몇분에 물이 차는지 저장합니다. ( 단 돌이 있는 위치는 물이 퍼질 수 없습니다. )
 각 칸들은 가능한 물이 퍼지는 시간 중 가장 낮은 값을 저장합니다.

(3) (코드: 31~54)
 현재위치 S 에서 BFS 을 통해 굴 D 까지의 경로를 탐색합니다.
 인접 칸으로 이동할때 시간을 저장하며 탐색하고, (과정 2에서 저장해놓은) 이동할 칸의 물이 퍼진시간이 더 작은 경우는 이동하지 못합니다.

(4) 굴에 도착 가능하면 저장해간 시간을 답으로 출력하고, 굴에 도착하지 못할 시 KAKTUS를 출력합니다.

	#include <bits/stdc++.h>
	using namespace std;
	const int INF = 1000;
	typedef pair<int, int> pii;
	// x 위치 , y 위치 , 시간
	typedef tuple<int, int, int> tp;
	int R, C;
	int ans = INF;
	// 물 : 0, 굴 : -1 , 돌 : INF
	int Forest[51][51];
	// 위쪽 오른쪽 아래쪽 왼쪽
	int dx[4] = {-1,0,1,0};
	int dy[4] = {0,1,0,-1};
	bool visited[51][51];
	queue<tp> Q;
	// 물을 먼저 퍼뜨림
	void Spread(int x, int y, int t){
	Forest[x][y] = min(Forest[x][y],t);
	for (int i = 0; i < 4; ++i){
	int nx = x+dx[i];
	int ny = y+dy[i];
	// 가능지역 밖
	if(nx<0||nx>=R||ny<0||ny>=C) continue;
	// 굴(-1) 인경우 or 이미 물이 펴진 경우
	if(Forest[nx][ny]<0||Forest[nx][ny]<=t+1) continue;
	Spread(nx,ny,t+1);
	}
	}
	// BFS
	void Findans(int x, int y){
	Q.push(tp(x,y,0));
	visited[x][y] = true;
	while(!Q.empty()){
	tp T = Q.front();
	Q.pop();
	int xnow = get<0>(T);
	int ynow = get<1>(T);
	int w = get<2>(T);
	if(Forest[xnow][ynow]==-1){
	ans = w;
	break;
	}
	for (int i = 0; i < 4; ++i){
	int nx = xnow+dx[i];
	int ny = ynow+dy[i];
	if(nx<0||nx>=R||ny<0||ny>=C) continue;
	if(Forest[nx][ny]==-2||(Forest[nx][ny]>=0&&Forest[nx][ny]<=w+1)) continue;
	if(visited[nx][ny]) continue;
	Q.push(tp(nx,ny,w+1));
	visited[nx][ny]=true;
	}
	}
	}
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> R >> C;
	pii Start;
	// 물 : 0, 굴 : -1 , 돌 : -2 , 통로 : INF
	for (int i = 0; i < R; ++i){
	for (int j = 0; j < C; ++j){
	char C;
	cin >> C;
	if(C=='*') Forest[i][j] = 0;
	else if(C == 'X') Forest[i][j] = -2;
	else if(C=='D')Forest[i][j] = -1;
	else {
	Forest[i][j] = INF;
	if(C=='S') Start = pii(i,j);
	}
	}
	}
	// 물부터 퍼뜨림
	for (int i = 0; i < R; ++i)
	for (int j = 0; j < C; ++j)
	if(Forest[i][j]==0) Spread(i, j, 0);
	// 경로 탐색
	Findans(Start.first,Start.second);
	if(ans==INF) cout << "KAKTUS" << '\n';
	else cout << ans << '\n';
	return 0;
	}

view raw BOJ 3055.cpp hosted with ❤ by GitHub