Softeer-연습문제-GINI야 도와줘(C++)

문제 링크 :

https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=583&sw_prbl_sbms_sn=41516

 

문제 개요 : 

소나기를 피해 몇 분만에 집에 도착하는지 구한다.

 

#include<iostream>
#include<vector>
#include<queue>
#include<tuple>

#define SPACE 100000


using namespace std;

int main(int argc, char** argv)
{
	// 입력
	int R,C;
	cin >> R >> C;
	queue<tuple<int,int,int>> rains; // 소나기 저장
	queue<tuple<int,int,int>> car; // 차 위치 저장
	int home[2]; // 집 위치 저장
	vector<vector<int>> W_map(R,vector<int>(C,SPACE)); // 차 지나가는 곳 저장
	vector<vector<int>> R_map(R,vector<int>(C,SPACE)); // 비 오는 곳 저장
	for(int i=0;i<R;i++){
		for(int j=0;j<C;j++){
			char tmp;
			cin >> tmp;
			switch(tmp){
				case'W': // 차 위치
				car.push(make_tuple(i,j,0));
				W_map[i][j]=0;
				break;
				case'H': // 집 위치
				home[0]=i; home[1]=j;
				R_map[i][j]=SPACE+1;
				break;
				case'*': // 소나기 위치
				R_map[i][j]=0;
				rains.push(make_tuple(i,j,0));
				break;
				case'X': // 강 위치
				W_map[i][j]=-1;
				R_map[i][j]=-1;
				break;
			}
		}
	}

	int dir[4][2] = {{1,0},{0,1},{-1,0},{0,-1}}; // 움직일 방향
	// R_map BFS
	while(!rains.empty()){
		int x = get<0>(rains.front());
		int y = get<1>(rains.front());
		int t = get<2>(rains.front());
		rains.pop();
		for(int i=0;i<4;i++){
			int nx = x + dir[i][0];
			int ny = y + dir[i][1];
			if(nx<0 || nx>=R || ny<0 || ny>=C || R_map[nx][ny]!=SPACE) continue; // 비가 지나가지 못하는 곳은 패스
			rains.push(make_tuple(nx,ny,t+1));
			R_map[nx][ny] = t+1;
		}
	}
	// W_map BFS
	while(!car.empty()){
		int x = get<0>(car.front());
		int y = get<1>(car.front());
		int t = get<2>(car.front());
		car.pop();
		for(int i=0;i<4;i++){
			int nx = x + dir[i][0];
			int ny = y + dir[i][1];
			if(nx<0 || nx>=R || ny<0 || ny>=C || W_map[nx][ny]!=SPACE || t+1>=R_map[nx][ny]) continue; // 차가 지나가지 못하는 곳은 패스
			car.push(make_tuple(nx,ny,t+1));
			W_map[nx][ny] = t+1;
		}
	}
	if(W_map[home[0]][home[1]]==SPACE) printf("FAIL"); // 차가 목적지에 도달하지 못함
	else printf("%d",W_map[home[0]][home[1]]); // 차가 목적지에 도달함

	return 0;
}

 

문제 해결 방법

1. 소나기 지도와 차 지도로 나누어 배열을 생성한다.

2. 소나기 지도 각 칸에 몇 분 뒤에 비가 오는지 기록한다. 이때 집과 강에는 비가 오지 않는다는 것을 고려해야 한다.

3. 차 지도 각 칸에 몇 분 뒤에 차가 도착하는지 기록한다. 이때 차는 강을 건널 수 없다는 것과 비가 오는 시간보다 늦게 도착하면 안된다는 것을 고려해야 한다.

4. 지도를 탐색할 때에는 BFS를 사용해야 한다.

5. 지도의 각 칸에 시간을 기록하는 시점이 중요한데, 큐에서 좌표를 꺼내고 시간을 저장하는 것이 아니라 큐에 좌표를 저장할 때 그 칸에 시간을 저장하는 것을 같이 처리해주어야 한다. 즉, 아래는 잘못된 코드이다.

	// R_map BFS
	while(!rains.empty()){
		int x = get<0>(rains.front());
		int y = get<1>(rains.front());
		int t = get<2>(rains.front());
		R_map[x][y] = t; // 이 시점에서 시간을 기록하면 안됨!!
		rains.pop();
		for(int i=0;i<4;i++){
			int nx = x + dir[i][0];
			int ny = y + dir[i][1];
			if(nx<0 || nx>=R || ny<0 || ny>=C || R_map[nx][ny]!=SPACE) continue;
			rains.push(make_tuple(nx,ny,t+1));
		}
	}
	// W_map BFS
	while(!car.empty()){
		int x = get<0>(car.front());
		int y = get<1>(car.front());
		int t = get<2>(car.front());
		W_map[x][y] = t; // 이 시점에서 시간을 기록하면 안됨!!
		car.pop();
		for(int i=0;i<4;i++){
			int nx = x + dir[i][0];
			int ny = y + dir[i][1];
			if(nx<0 || nx>=R || ny<0 || ny>=C || W_map[nx][ny]!=SPACE || t+1>=R_map[nx][ny]) continue;
			car.push(make_tuple(nx,ny,t+1));
		}
	}