백준 3197 - 백조의 호수 (C++, 복습)

문제 링크입니다! https://www.acmicpc.net/problem/3197

3197번: 백조의 호수

문제 조건

출력 예시

1. 백조를 먼저 이동시켜본다.

2. 백조가 못만났을 경우 얼음을 녹인다.

3. 1번과 2번을 반복한다.

-> 이 방법이 가장 생각하지 쉬운 방법입니다. 하지만 시간초과가 나는 방법이였습니다.

 

시간 초과가 나지 않는 다른 방법은 

1. 백조를 이동시킨다.

2. 백조가 얼음을 만났을 경우 다음 탐색에서 시작할 좌표임으로 큐에 넣어준다.

3. 백조가 못만났을 경우 얼음을 녹인다.

4. 큐에 넣어준 좌표에서 다시 시작한다.

5. 1~4번을 반복한다.

-> 해당 방법이 시간 초과가 나지 않는 효율적인 방법입니다. 

 

예시를 통해서 방법을 확인해 보겠습니다.

빨간색 - 다음에 탐색 시작할 위치

이런 방식으로 탐색을 한다면 빠르게 답을 얻을 수 있습니다.

 

문제 접근 방법

1. 물의 위치와 백조의 위치를 저장한다.

2. 1번 백조의 위치에서 탐색을 시작한다.(BFS)

3. 백조들이 만나지 못했을 경우 -> 얼음을 녹인다.

4. 2~3번을 백조가 만날 때까지 반복한다.

 

문제 접근 방법 - 2번 + 3번 + 4번(solve() + bfs() + melt_ice() 함수를 참고해주세요)

1. bfs() 함수

   1번째 백조의 위치에서 탐색을 시작합니다. 상하좌우로 이동하는 중, 3가지 경우가 있습니다.

   1. 다음 좌표가 물인 경우 -> 좌표를 큐에 넣어줘서 탐색해줍니다.

   2. 다음 좌표가 백조인 경우 -> 탐색을 종료한 뒤, 기간을 출력합니다.

   3. 다음 좌표가 얼음인 경우 -> 바로 다음에 탐색할 수 있으니 next queue에다가 넣어줍니다.

   얼음인 경우에서 바로 탐색할 수 있는 이유는 백조가 물 -> 얼음으로 이동합니다. 따라서 백조가 이동한 얼음은 바로     다음 순서에서 녹는다는 것을 알수 있습니다. 따라서 next queue에다가 넣어줌으로서 탐색을 이어나가게 해줍니다.

2. melt_ice() 함수

   물의 좌표에서 상하좌우에 얼음이 있다면 바로 녹일 수 있는 얼음입니다. 따라서 얼음을 녹인 뒤, 다음 얼음을 녹이기     위해서 next queue에 넣어줍니다. 

3. solve() 함수

   bfs() 함수를 통해서 백조들이 만났는지의 여부를 확인합니다. 만나지 못했다면 얼음을 녹입니다. 이 과정에서 백조의     위치, 얼음의 위치가 각각의 next queue에 저장되어 있습니다. 따라서 원래의 queue에 전부 넣어준뒤 pop 해줍니다.

 

자세한 것은 코드를 참고해주세요!

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>

using namespace std;

int N, M;
char map[1501][1501];
char copy_map[1501][1501];
int check[1501][1501];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
vector<pair<int, int>> swan;
queue<pair<int, int>> swan_q, swan_next, ice_q, ice_next;

bool bfs() {	
	pair<int, int> finish = swan[1];
	while (!swan_q.empty()) {
		int x = swan_q.front().first;
		int y = swan_q.front().second;
		swan_q.pop();
		if (x == finish.first && y == finish.second) {
			return true;
		}
		for (int i = 0; i < 4; i++) {
			int xx = x + dx[i];
			int yy = y + dy[i];
			if (xx >= 1 && yy >= 1 && xx <= N && yy <= M) {
				if (check[xx][yy] == 0 && map[xx][yy] != 'X') {
					check[xx][yy] = 1;
					swan_q.push(make_pair(xx, yy));
				}
				else if (check[xx][yy] == 0 && map[xx][yy] == 'X') {
					check[xx][yy] = 1;
					swan_next.push(make_pair(xx, yy));
				}
			}
		}
	}
	return false;
}

void melt_ice() {
	while (!ice_q.empty()) {
		int x = ice_q.front().first;
		int y = ice_q.front().second;
		ice_q.pop();
		for (int i = 0; i < 4; i++) {
			int xx = x + dx[i];
			int yy = y + dy[i];
			if (xx >= 1 && yy >= 1 && xx <= N && yy <= M) {
				if (map[xx][yy] == 'X') {
					map[xx][yy] = '.';
					ice_next.push(make_pair(xx, yy));
				}
			}
		}
	}
}

void solve() {
	swan_q.push(swan[0]);
	check[swan[0].first][swan[0].second] = 1;
	int ans = 0;
	while (1) {
		if (bfs()) {
			break;
		}
		else {
			melt_ice();
			ice_q = ice_next;
			swan_q = swan_next;
			while (!ice_next.empty()) ice_next.pop();
			while (!swan_next.empty()) swan_next.pop();
			ans++;
		}
	}
	cout << ans;
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cin >> map[i][j];
			if (map[i][j] != 'X') ice_q.push(make_pair(i, j));
			if (map[i][j] == 'L') swan.push_back(make_pair(i, j));
		}
	}
	solve();
	return 0;
}

 

 

질문 및 조언 댓글 남겨주세요!