PS) 2178, 1697, 18870번 (미로 찾기, 숨바꼭질, 좌표 압축)

 

2178번 미로 찾기

 

bfs이므로 현재 방문할 수 있는 노드를 그냥 탐색하면서 탐색횟수를 저장해주면 된다.

탐색한 노드는 다시 방문하지 않아도 된다 (저장한 탐색 횟수가 1,1에서 현재 노드로 가는 최소 거리로 확정된다).

이후 탐색하는 과정에서 이미 탐색한 노드로 길이 이어질 수 있지만 그 경로는 다른 노드를 몇번 거쳐서 오는 것이므로(bfs이므로! ) 최소 거리가 아니고, 따라서 고려할 필요가 없다.

처음에는 최소 거리일 때, 저장한다라는 조건을 주어서 구현하였는데 굳이 이 조건은 필요가 없다. 탐색하면서 거리를 저장해주고, 방문을 기록해주고 반복하는 식으로 하면 된다.

 

#include<stdio.h>
#include<string>
#include<queue>
using namespace std;
int arr[105][105];
int minarr[105][105];
queue<pair<int, int>>q;
int tox[4] = { 0,0,-1,1 };	int toy[4] = { 1,-1,0,0 };

void bfs(int n,int m) { //탐색 & set min
	q.push({ 1,1 });
	pair<int, int> node; int x; int y;
	int cycle = 0; int sum = 0; int prevsum = 1;
	while (q.empty()==false) {
		while (prevsum > 0) {
			node = q.front(); x = node.first; y = node.second;
			for (int i = 0; i < 4; i++) {
				int nx = x + tox[i];
				int ny = y + toy[i];
				if (arr[nx][ny] == 1 && nx <= n && nx > 0 && ny > 0 && ny <= m) {
					if (minarr[nx][ny] > cycle + 1) {
						minarr[nx][ny] = cycle + 1; sum++;
						q.push({ nx,ny });
					}
				}
			}
			q.pop(); prevsum--;
		}
		prevsum = sum; sum = 0;
		cycle++;
	}
	printf("%d", minarr[n][m] + 1);
}
int main() {
	// 1,1 to n,m
	int n, m; scanf("%d%d", &n, &m);
	int a;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			scanf("%1d", &a);
			arr[i][j] = a; minarr[i][j] = 10000000;
		}
	}
	bfs(n, m);
}

 

 

1697번 숨바꼭질

 

dp인줄 알았다. dp로 풀다보니 예외처리해주어야 할 부분이 많았고 계속 틀렸습니다가 떴다. 

 

결국 알아차리고 bfs로 풀어 보니 그리 어렵지 않았다. 하지만 만약 이 문제를 bfs로 풀어야 한다는 것을 알아차리지 못했다면...? 생각만해도 답답하다. 문제를 보고, 어떤 유형인지 파악하는 것이 중요한 것 같다. 

 

dp와 그래프 탐색(bfs dfs)유형은 얼핏 보기에 비슷해 보일 수 있다.

배열에 정보를 메모이제이션한다는 점이 동일하기 때문이다. 그래서 여러 문제에서 초반에 헷갈렸다. 

음 둘의 차이점을 생각해보니..

 

그래프 탐색

• 기본적으로 탐색★하는 문제인 경우

 

DP

• 이전의 경우로 이후의 경우를 계산할 수 있는 경우 (한방향으로 점화식이 수립될 수 있는 경우)
• 모든 경우를 다 고려해주어야 하는 경우 (그래프의 경우 갈 수 있는 경로만 따라가면 됨) 

 

이때까지 풀어본 문제에서 생각한 것들이라서 앞으로 더 어려운 유형을 만나게 되면 수정이 필요할지도..

 

이 경우에는 i에서 i-1, i+1, i*2로 이동할 수 있다. dp로 풀게 되면 i-1에서 문제가 생긴다. 이전의 경우로 이후의 경우를 계산할 수 없다. 이전으로 다시 돌아가야 하는 경우도 생각해줘야 하기 때문에 이상한 사이클이 생길 수 있다. 

 

따라서 i 노드가 i-1, i+1, i*2노드와 연결되어 있다고 생각하고, n노드에서 k노드로 가는 경로를 bfs로 찾아주어야 한다. 

 

#include<stdio.h>
#include<queue>
#include<vector>
using namespace std;
int arr[200005];
int isvisit[200005];
queue<int> q;

void bfs(int n,int k) {
	q.push(n);
	int node; isvisit[n] = 1;
	while (q.empty()==false) {
		node = q.front();
		if (node - 1 >= 0 && isvisit[node-1]==0) {
			q.push(node - 1); isvisit[node - 1] = 1; arr[node-1] = arr[node] + 1;
		}
		if (node + 1 <= k * 2 && isvisit[node+1]==0) {
			q.push(node + 1); isvisit[node + 1] = 1; arr[node+1] = arr[node] + 1;
		}
		if (node * 2 <= k * 2 && isvisit[node*2]==0) {
			q.push(node * 2); isvisit[node * 2] = 1; arr[node*2] = arr[node] + 1;
		}
		q.pop();
		if (isvisit[k] == 1) return;
	}
}
int main() {
	int n, k; scanf("%d%d", &n, &k);
	bfs(n, k);
	printf("%d", arr[k]);
}

 

7 10
1
1 2 3
1 3 1
2 3 2
2 5 5
3 5 6
3 6 1
3 4 2
4 6 8
5 6 7
6 7 1

 

18870번 좌표 압축

 

#include<stdio.h>
#include<map>
using namespace std;
multimap<int, int> m;
multimap<int, int>::iterator iter;
int arr[1000005];
int main() {
	int n; scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &arr[i]);
		m.insert({ arr[i],i });
	}
	iter = m.begin();
	int index = 0; int prev;

	arr[(*iter).second] = index;
	prev = (*iter).first;

	while (iter != m.end()) {
		if ((*iter).first != prev) {
			index++;
		}
		arr[(*iter).second] = index;
		prev = (*iter).first;
		iter++;
	}
	for (int i = 1; i <= n; i++) printf("%d ", arr[i]);
}