해결된 질문2022-10-23T08:35:51.478Z

yeon _leaf

작성한 질문수 22

1

한개 빼고는 잘 짜셨습니다.ㅎㅎ 백조의 호수는 좀 타이트해서 맞는 코드인데도 시간초과가 발생하기도 해요. 제가 해답코드로 제시한 코드 조차도 몇개 코드만 좀 수정하면 (맞는 로직인데도) 시간초과가 발생합니다.

그냥 이런 문제는 이런 거구나 하고 넘기시면 될 거같아요. 또한 yeon님 코드 피드백 드렸으니 참고부탁드려요.

#include <bits/stdc++.h>
using namespace std;
//good 근데 이거 범위가 1500이라서 2000을 줘도 되요. 
const int base = 2253001;
int r, c;
char board[1501][1501];
int v1[1501][1501];
int v2[1501][1501]; 
int si, sj;
queue<int> water;
queue<int> swan;
int days;

int di[] = {-1, 0, 1, 0};
int dj[] = {0, 1, 0, -1};


void melting() {
	queue<int> tmp1;
	// good
	while (water.size()) {
		int cl = water.front(); water.pop();
		int ci = cl / base;
		int cj = cl % base;
		for (int d=0; d<4; d++) {
			int ni = ci + di[d];
			int nj = cj + dj[d];
			if (ni < 0 || nj < 0 || ni >= r || nj >= c || v1[ni][nj] || board[ni][nj] == 'L') continue;
			if (board[ni][nj] == 'X') {
				v1[ni][nj] = 1;
				board[ni][nj] = '.';
				tmp1.push(base * ni + nj);
				continue;
			}
			v1[ni][nj] = 1;
			water.push(base * ni + nj);
		}
	}
	water = tmp1;
}

bool move_swan() {
	queue<int> tmp2;
	bool flag = 0;
	while (swan.size()) {
		int cl = swan.front(); swan.pop();
		int ci = cl / base;
		int cj = cl % base;
		// good
		for (int d=0; d<4; d++) {
			int ni = ci + di[d];
			int nj = cj + dj[d];
			if (ni < 0 || nj < 0 || ni >= r || nj >= c || v2[ni][nj]) continue;
			//good
			if (board[ni][nj] == 'L') {
				flag = 1;
				break;
			}
			if (board[ni][nj] == 'X') {
				v2[ni][nj] = 1;
				tmp2.push(base * ni + nj);
				continue; 
			}
			v2[ni][nj] = 1;
			swan.push(base * ni + nj);
		}
		if (flag) break;
	}
	swan = tmp2;
	return flag;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	cin >> r >> c;
	
	for (int i=0; i<r; i++) {
		string line;
		cin >> line;
		for (int j=0; j<c; j++) {
			board[i][j] = line[j];
			//백조여도 물에다 푸시해줘야해요. 백조는 물위에 떠있는거니까요. 
			if (board[i][j] == 'L') {
				si = i; sj = j;
			}
			
			if (board[i][j] == '.') {
				v1[i][j] = 1;
				water.push(base*i + j);
			}
		}
	}
	
	swan.push(base * si + sj);
	v2[si][sj] = 1;
	
	while (true) {
		bool test = move_swan();
        if (test) break;
		melting();
		days++;
	}
	
	cout << days << "\n";
	
	return 0;
}