백준 20130 (Metroidvania Extreme)

www.acmicpc.net/problem/20130

20130번: Metroidvania Extreme

이 문제를 풀면서 감탄을 정말 많이 했다. 

 

일단 bfs문제인데, bfs의 성질을 잘 알아야 순간이동이 무슨소리인지 이해가 될거라고 생각한다. 

 

개인적으로 무슨 소리인지 모르겠으면 혼자 깨달을때까지 생각해보는거 추천

 

이 문제의 핵심은 bfs로 풀 수 있다는 걸 아는 것이라고 생각한다. 

그리고 a가 없이 A를 만났을때 어떻게 해야할지 아는것? 생각하면 된다. 

그냥 어떻게 자료를 저장하고 후에 처리를 할지 생각해보자 

 

자료를 어떻게 저장 처리할지는 어떤 방식으로 작동하는지 생각하면 알 수 있다.

 

뭐 나머지는 그냥 구현에서의 주의점? 

 

이 문제에서는 주의할 점이 여러개가 있다. 

 

제일 헤맨부분은 a,A가 최대 하나라고 생각하고 풀었었다. 최소와 최대갯수는 정해지지 않아있다. 

그리고 visit을 언제할지, queue에 언제 넣을지 주의해야하는 것 같다. 

 

진짜 좋은 문제라고 생각한다. 

 

#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
#define MAX 205

queue<pair<int, int> > q;
queue<pair<int, int> > ans;
queue<pair<int, int> > v[MAX];
pair<int, int> start;
pair<int, int> fin;
int N, M;
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
char mat[MAX][MAX];
bool visit[MAX][MAX];
bool haveal[MAX];

void bfs() {
	q.push(start);
	visit[start.first][start.second] = true;
	ans.push(start);
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx == fin.first && ny == fin.second) {
				ans.push(fin);
				return;
			}
			if (visit[nx][ny] || mat[nx][ny] == '#')continue;
			int a = (int)mat[nx][ny];
			if (a >= 65 && a <= 90 && !haveal[a + 32]){
				v[a + 32].push({ nx,ny });
				continue;
			}
			visit[nx][ny] = true;
			q.push({ nx,ny });
			ans.push({ nx,ny });
			if (a >= 97 && a <= 122) {
				haveal[a] = true;
				while(!v[a].empty()){
					int k = v[a].front().first;
					int l = v[a].front().second;
					v[a].pop();
					if (!visit[k][l]) {
						visit[k][l] = true;
						ans.push({ k,l });
						q.push({ k,l });
					}
				}
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			char a;
			cin >> a;
			mat[i][j] = a;
			if (a == '@') {
				start.first = i;
				start.second = j;
			}
			if (a == '!') {
				fin.first = i;
				fin.second = j;
			}
		}
	}
	bfs();
	cout << ans.size() << "\n";
	while (!ans.empty()) {
		cout << ans.front().first << " " << ans.front().second << "\n";
		ans.pop();
	}
}