[Softeer 🌟🌟🌟] GINI야 도와줘(C++)

※주의※

저의 풀이가 정답은 아닙니다.

다른 코드가 더 효율적이거나 좋을 수 있습니다.

언제나 다른 사람의 코드는 참고만 하시기 바랍니다.

 

 

[문제 풀이 사이트]

 

 

Softeer

 

 

[문제 설명]

 

 

GINI는 현대자동차그룹에서 개발한 네비게이션이다. GINI는 너무나도 뛰어나 목적지에 도착하는 시간을 예측할 수 있다. 어느 날 태범이는 세차장에서 세차를 하고 집에 돌아가려고 하는데 소나기가 몰려오고 있다는 뉴스를 전해 들었다. 태범은 방금 세차한 차를 지키기 위해 GINI를 사용하여 무사히 집에 귀환하고자 한다!

 

지도는 R행과 C열로 이루어져있다. 비어있는 칸은 ‘.’로 표시되고, 소나기는 ‘*’로, 강은 ‘X’로 표시되어있다. 태범이의 집은 ‘H’로 표현되고, 태범이가 처음있던 세차장의 위치는 ‘W’로 표시된다.

 

매 분마다 태범이는 인접한 네 개의 칸(상, 하, 좌, 우)으로 이동할 수 있다. 소나기는 매 분마다 인접한 네 개의 칸(상, 하, 좌, 우)으로 확산한다. 태범이는 소나기와 강을 지나지 못하며, 소나기는 강과 태범이의 집에 옮겨지지 않는다.(소나기는 강으로 가면 소멸) 태범이가 무사히 집에 도착할 수 있을 때 몇 분 만에 도착할 수 있는 예측하는 GINI 네비게이션 프로그램을 만들어보자.

 

 

[제약조건]

 

 

R, C ≤ 50

‘H’와,’W’는 하나씩만 주어진다.

 

 

[입력형식]

 

 

첫째 줄에 R과 C가 주어진다. 다음 N개 줄에는 지도가 주어지며, 문제에서 설명한 문자만 주어진다.

 

 

[출력형식]

 

 

첫째 줄에 태범이가 집으로 갈 수있는 가장 빠른 시간을 출력한다. 만약 소나기를 피해 집에 도착할 수 없다면 “FAIL”을 출력한다.

 

 

[입출력 예]

 

 

입력	출력
4 3 H.* ... XXX W..	FAIL
3 3 H.* ... W..	2

 

 

[문제 풀이]

 

 

쉬운 BFS 문제이다.

마치 백준 5427번 불과 비슷했다.

[BaekJoon 5427번] 불(C++)

 

➔ 필요한 변수

• 지도에 대한 입력을 저장할 배열
• 소나기 위치 좌표에 대한 이동 시간을 저장할 배열
• 태범이의 위치 좌표에 대한 이동 시간을 저장할 배열
• 소나기의 위치 좌표를 저장할 큐
• 태범이의 위치 좌표를 저장할 큐
• 태범이의 집 위치(X, Y)를 저장할 변수 

 

 

지도에 대한 입력을 받을 때

• 소나기 위치 좌표에 대한 이동 시간을 저장할 배열과 태범이의 위치 좌표에 대한 이동 시간을 저장할 배열을 fill 함수를 통해 -1로 초기화 시킨다.
• 지도의 위치 좌표가 태범이('W' 세차장 위치)이면 태범이의 위치 좌표를 큐에 넣는다. 그리고 태범이의 위치 좌표에 대한 이동 시간을 0으로 저장한다.
• 소나기의 위치 좌표가 소나기('*')이면 소나기의 위치 좌표를 큐에 넣는다. 그리고 소나기의 위치 좌표에 대한 이동 시간을 0으로 저장한다.

 

먼저 소나기에 대한 BFS 알고리즘을 사용하고

raintime[nx][ny] = raintime[cur.first][cur.second] + 1;

➔ 다음 소나기의 위치 좌표 = 현재 소나기의 위치 좌표 + 1을 통해 소나기의 이동시간을 계산해주었다.

 

 

그리고 태범이에 대한 BFS 알고리즘을 사용했다.

태범이의 다음 위치를 계산할 때

이미 방문했던 위치나 다음 위치가 강이거나 소나기인 경우

그리고 소나기가 먼저 이동한 위치 또는 소나기와 동시에 이동한 위치로는 이동할 수 없기 때문에

if(bumtime[nx][ny] != -1 || board[nx][ny] == '*' || board[nx][ny] == 'X') continue;
if(raintime[nx][ny] != -1 && raintime[nx][ny] <= bumtime[cur.first][cur.second] + 1) continue;

아래 조건을 넣음으로서 해결했다.

 

그리고 태범이의 BFS 알고리즘이 끝나면

태범이의 위치 좌표에 대한 이동 시간이 저장되어 있는 배열에서

태범이의 집 위치 좌표일 때 초기값이 아니라면 집에 갔다는 의미가 되므로 해당 값을 출력해주었고

초기값이라면 가지못했으므로 FAIL을 출력해주었다.

 

 

[최종 코드]

 

 

[GitHub]

 

 

GitHub - SmallPeanutPark/Softeer: Softeer HYUNDAI

 

 

#include <iostream>
#include <algorithm>
#include <queue>
#include <utility>

using namespace std;

string board[51];
int bumtime[51][51];
int raintime[51][51];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int main(int argc, char** argv)
{
	int R, C; cin >> R >> C;
	int homeX = 0;
	int homeY = 0;
	queue<pair<int, int>> bum;
	queue<pair<int, int>> rain;
	for(int i = 0; i < R; ++i) {
		cin >> board[i];
		fill(bumtime[i], bumtime[i] + 51, -1);
		fill(raintime[i], raintime[i] + 51, -1);
		for(int j = 0; j < C; ++j) {
			if(board[i][j] == 'W') {
				bum.push({i,j});
				bumtime[i][j] = 0;
			}

			if(board[i][j] == '*') {
				rain.push({i, j});
				raintime[i][j] = 0;
			}

			if(board[i][j] == 'H') {
				homeX  = i;
				homeY = j;
			}
		}
	}

	// 소나기 bfs
	while(!rain.empty()) {
		pair<int, int> cur = rain.front();
		rain.pop();
		for(int i = 0; i < 4; ++i) {
			int nx = cur.first + dx[i];
			int ny = cur.second + dy[i];
			if(nx < 0 || nx >= R || ny < 0 || ny >= C) continue;
			if(raintime[nx][ny] != -1 || board[nx][ny] == 'X' || board[nx][ny] == 'H') continue;
			rain.push({nx, ny});
			raintime[nx][ny] = raintime[cur.first][cur.second] + 1;
		}
	}

	// 태범 bfs
	while(!bum.empty()) {
		pair<int, int> cur = bum.front();
		bum.pop();
		for(int i = 0; i < 4; ++i) {
			int nx = cur.first + dx[i];
			int ny = cur.second + dy[i];
			if(nx < 0 || nx >= R || ny < 0 || ny >= C) continue;
			if(bumtime[nx][ny] != -1 || board[nx][ny] == '*' || board[nx][ny] == 'X') continue;
			if(raintime[nx][ny] != -1 && raintime[nx][ny] <= bumtime[cur.first][cur.second] + 1) continue;
			bum.push({nx, ny});
			bumtime[nx][ny] = bumtime[cur.first][cur.second] + 1;
		}
	}
	if(bumtime[homeX][homeY] != -1) {
		cout << bumtime[homeX][homeY];
	} else {
		cout << "FAIL";
	}
}