알고리즘 스터디 - 큐

https://www.acmicpc.net/problem/14226

14226번: 이모티콘

 

솔루션

---

처음에 접근법이 잘 안떠올라 고생했다.

 

기존의 BFS와 유사한데, 복사라는 기능이 추가되어 까다로웠다.

 

나는 2차원 배열로 잡고, 우선순위 큐를 이용해 해결하였다.

 

우선순위 큐는

{텍스트 길이, 복사된 문자 길이, 총 시간} 으로 잡고 정렬 순서는

시간이 가장 작은 것이 top에 위치 하도록 하였다.

 

그리고 시작은 {1,0,0}으로 시작하여서 다음 3가지 경우로 나눴다.

 

1. 현재 이모티콘을 복사하여 다시 붙여넣는경우

 이때는 시간이 2초 소모되며, 텍스트 길이는 2배, 복사된 문자 길이는 텍스트 길이, 시간은 +2 가 된다.

 

2. 복사된 이모티콘을 또 붙여넣는 경우

 이때는 시간 1초 소모되며, {텍스트 길이 + 복사된 문자 길이, 복사된 문자 길이, 시간+1} 이 되며

 

3. 문자 하나를 지우는 겨웅

시간이 1초 소모 되며 {텍스트 길이 - 1, 복사된 문자 길이, 시간+1} 이 된다.

 

그리고 우선순위 큐를 이용하였으므로 S에 도달하게 되면 가장 작은 최소값이므로 바로 출력하고 종료한다.

 

 

코드

---

#define INF 987654321
#include <iostream>
#include <queue>
using namespace std;

struct pa {
	int num, copy, cnt;
	bool operator<(const struct pa& t)const {
		if (cnt == t.cnt) {
			return num > t.num;
		}
		return cnt > t.cnt;
	}
};

int arr[2002][2002];
priority_queue<pa> Q;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int N;
	cin >> N;

	for (int i = 1; i <= 2000; i++) {
		for (int j = 1; j <= 2000; j++) arr[i][j] = INF;
	}

	Q.push({ 1,0,0 });
	int ans = INF;

	while (!Q.empty()) {
		int cur = Q.top().num;
		int copy = Q.top().copy;
		int cnt = Q.top().cnt;
		Q.pop();

		if (cur> N+200) continue;
		if (cnt > arr[cur][copy]) continue;
		if (cur == N) {
			cout << cnt << '\n';
			return 0;
		}

		if (cur + cur <= 1200 && arr[cur+cur][cur]  > cnt+2) {
			Q.push({ cur + cur,cur,cnt + 2 });
			arr[cur + cur][cur] = cnt + 2;
		}
		if (cur + copy <= 1200 && arr[cur + copy][copy] > cnt + 1) {
			Q.push({ cur + copy,copy,cnt+1});
			arr[cur + copy][copy] = cnt + 1;
		}
		if (cur - 1 > 1 && arr[cur - 1][copy] > cnt + 1) {
			Q.push({ cur - 1,copy,cnt +1});
			arr[cur - 1][copy] = cnt + 1;
		}

	}
}

 

 

---

 

 

 

https://www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

 

솔루션

---

처음에 밑/오른쪽으로만 갈 수 있다고 생각하여서 문제를 접근하였다가 정답이 나오지 않아서 문제를 다시 읽었다.

 

 

상하좌우 다 움직일 수 있도록 하였고, 또한 벽을 부술 수 있는 것은 1개 이기 때문에 3차원 배열을 만들어서 해결하였다.

 

[2][N][M] 사이즈로 배열을 잡아서 해결하였고, 벽을 부수지 않았다면 [0][x][y]에 초기화 하였고

벽을 부수고 온 지점이라면 [1][x][y]로 처리 하여서 N,M지점에 도착했을 때 총 움직인 회수를 출력하였다.

 

 

코드

---

#include <iostream>
#include <queue>
using namespace std;

bool visit[2][1002][1002];
struct pa {
	int x, y, c;
	bool b;
};
string str[1002];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int N, M;
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		cin >> str[i];
	}
	
	queue<pa> Q;
	Q.push({ 0,0,1,false });

	int ans = -1;
	while (!Q.empty()) {
		pa cur = Q.front();
		Q.pop();

		if (cur.x +1== N && cur.y+1 == M) {
			if (ans == -1) {
				ans = cur.c;
			}
			else {
				ans = min(cur.c, ans);
			}
		}
		for (int i = 0; i < 4; i++) {
			int tx = dx[i] + cur.x;
			int ty = dy[i] + cur.y;
			
			if (tx >= 0 && tx < N && ty >= 0 && ty < M) {
				if (str[tx][ty] == '1' && !cur.b&& !visit[1][tx][ty]) {
					Q.push({ tx,ty,cur.c + 1, true });
					visit[1][tx][ty] = true;
				}
				if(str[tx][ty] == '0'&& !visit[cur.b][tx][ty]) {
					Q.push({ tx,ty,cur.c + 1,cur.b });
					visit[cur.b][tx][ty] = true;
				}
			}
		}
	}

	cout << ans << '\n';
}