아직 계정이 없으신가요? 회원가입

Dev. Talk

[GINI야 도와줘] 문제에 대한 개인적인 생각

회원사진iamstar97
43 views2023-01-20 11:45

문제를 풀며 들었던 개인적인 생각입니다.


문제에 

'태범이는 소나기와 강을 지나지 못하며, 소나기는 강과 태범이의 집에 옮겨지지 않는다.(소나기는 강으로 가면 소멸)'

부분이 있습니다.


저는 처음 문제를 읽고 '강쪽으로는 비가 퍼지지 않지만, 집으로는 퍼질 수 있다.' 로 이해했습니다. 이 말은 집에는 비가 옮겨지지 않지만, 집 위에는 비구름이 존재해 시간이 지난 후에 계속 퍼질 수 있다는 뜻입니다.

예를 들면, 

. . . H . * -> . . . H * * -> . . . H * * (H위에 비구름 존재) -> . .  * H * * -> .  * * H * *


하지만, 이 방법으로 제출하면 틀리더라구요. 집도 강처럼 비가 퍼질 수 없게 설정해놔야 맞을 수 있었습니다.

제가 생각한 방법이 문제에서 제시한 조건과 맞다고 생각하는데 어떻게 생각하시나요???

혹시 몰라 코드도 올려놓겠습니다. 자유롭게 말씀 부탁드리겠습니다!



#include <iostream>
#include <string.h>
#include <vector>
#include <queue>

using namespace std;

struct pos {
	int x, y;
};

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

int R, C;
char map[50][50];
pos taebumStart, taebumEnd;
vector<pos> rainStart;
int answer;

bool isInner(pos p) {
	if (p.x < 0 || p.y < 0 || p.x >= R || p.y >= C) return false;
	return true;
}

void solution() {
	queue<pos> taebum, rain;
	bool taebumVisited[50][50];
	int clock = 0;
	memset(taebumVisited, false, sizeof(taebumVisited));

	taebum.push(taebumStart);
	taebumVisited[taebumStart.x][taebumStart.y] = true;
	for (pos& rs : rainStart) rain.push(rs);

	while (!taebum.empty()) {
		clock++;

		//소나기 이동
		int rainSize = rain.size();
		while (rainSize--) {
			pos cur = rain.front();
			rain.pop();

			for (int i = 0; i < 4; i++) {
				pos nxt = cur;
				nxt.x += dx[i], nxt.y += dy[i];
				if (isInner(nxt) && map[nxt.x][nxt.y] == '.') {
					//이렇게 하면 틀림
					//rain.push(nxt);
					//if (!(nxt.x == taebumEnd.x && nxt.y == taebumEnd.y)) {
					//	map[nxt.x][nxt.y] = '*';
					//}
					if (!(nxt.x == taebumEnd.x && nxt.y == taebumEnd.y)) {
						rain.push(nxt);
						map[nxt.x][nxt.y] = '*';
					}
				}
			}
		}

		//태범 이동
		int taebumSize = taebum.size();
		while (taebumSize--) {
			pos cur = taebum.front();
			taebum.pop();

			for (int i = 0; i < 4; i++) {
				pos nxt = cur;
				nxt.x += dx[i], nxt.y += dy[i];
				if (isInner(nxt) && !taebumVisited[nxt.x][nxt.y] && map[nxt.x][nxt.y] == '.') {
					if (nxt.x == taebumEnd.x && nxt.y == taebumEnd.y) {
						answer = clock;
						return;
					}
					taebum.push(nxt);
					taebumVisited[nxt.x][nxt.y] = true;
				}
			}
		}
	}
}

int main() {
	//초기화
	R = 0, C = 0;
	memset(map, 0, sizeof(map));
	answer = -1;

	//입력
	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] == 'W') {
				taebumStart = { i, j };
				map[i][j] = '.';
			}
			else if (map[i][j] == 'H') {
				taebumEnd = { i, j };
				map[i][j] = '.';
			}
			else if (map[i][j] == '*') rainStart.push_back({ i, j });
		}
	}

	//해법
	solution();

	//출력
	if (answer == -1) cout << "FAIL" << "\n";
	else cout << answer << "\n";

	//종료
	return 0;
}