<유사문제>
1261 알고스팟 https://www.acmicpc.net/problem/1261
2842 집배원 한상덕 https://www.acmicpc.net/problem/2842
5558 치~즈 https://www.acmicpc.net/problem/5558
9376 탈옥 https://www.acmicpc.net/problem/9376 (X)
1857 발레리노 https://www.acmicpc.net/problem/1857 (X)
보통 최단거리가 아닌(또는 포함) 다른 조건을 최소화 하는 문제는 다익스트라 알고리즘이나 우선순위 큐를 사용하여 해결할 수 있다.
1. 거울 설치 (★★★☆☆)
거울 위치마다 방문여부를 판단해서 설치할경우(2방향), 설치 안할경우(1방향)에 대해 BFS를 돌린다.
(일종의 다익스트라로 거울 설치 개수를 비교하며 최소일 경우 갱신하며 나아간다.)
<만든 테스트 케이스>
8
***#****
*!.!..!*
*......*
*..*...*
*!!....*
*.!!..!*
*......*
***#****
5
***#!
*.*..
*!.*.
*!..!
*#***
8
****!.#!
*...!..!
*.......
#......!
*......*
*......*
*......*
********
5
*#***
*.*.*
*!.*.
*!..!
*#***
8
****!.#!
*...!..!
*.......
#...!..!
*......*
*......*
*......*
********
#include <cstdio>
#include <queue>
#define INF 888888
using namespace std;
int N, ans = INF;
char map[51][51];
int visit[51][51][4];
bool check(int y, int x){
if (y < 0 || y >= N || x < 0 || x >= N) return true;
return false;
}
void bfs(int iy, int ix, int ey, int ex){
int dy[4] = { -1, 0, 0, 1 }, dx[4] = { 0, 1, -1, 0 }; //상, 우, 좌, 하
queue<pair<int, pair<int, int>>> q; //거울 개수,위치, 방향
for (int i = 0; i < 4; i++){
if (check(iy + dy[i], ix + dx[i])) continue;
if (map[iy + dy[i]][ix + dx[i]] != '*'){ //'#'위치에서 네방향 탐색
q.push({ 0, { (iy + dy[i])*N + ix + dx[i] , i } });
}
}
while (!q.empty()){
int mir = q.front().first;
int y = q.front().second.first / N, x = q.front().second.first % N;
int dir = q.front().second.second;
q.pop();
if (y == ey && x == ex){
ans = ans > mir ? mir : ans; //도착
continue;
}
if (map[y][x] == '!'){
if (visit[y][x][dir] > mir){
visit[y][x][dir] = mir;
if (dir == 0 || dir == 3){ //방향 상,하 일경우
int ly = y + dy[2], lx = x + dx[2]; //좌
int ry = y + dy[1], rx = x + dx[1]; //우
if (!check(ly, lx) && map[ly][lx] != '*')
q.push({ mir + 1, { ly*N + lx, 2 } });
if (!check(ry, rx) && map[ry][rx] != '*')
q.push({ mir + 1, { ry*N + rx, 1 } });
}
else if (dir == 1 || dir == 2){ //방향 좌,우 일경우
int uy = y + dy[0], ux = x + dx[0]; //상
int doy = y + dy[3], dox = x + dx[3]; //하
if (!check(uy, ux) && map[uy][ux] != '*')
q.push({ mir + 1, { uy*N + ux, 0 } });
if (!check(doy, dox) && map[doy][dox] != '*')
q.push({ mir + 1, { doy*N + dox, 3 } });
}
int ny = y + dy[dir], nx = x + dx[dir];
if (!check(ny, nx) && map[ny][nx] != '*'){ //이전 방향대로 이동
q.push({ mir, { ny*N + nx, dir } });
}
}
continue; //뒷부분 넘어감
}
int ny = y + dy[dir], nx = x + dx[dir];
if (!check(ny, nx) && map[ny][nx] != '*'){ //이전 방향대로 이동
q.push({ mir, { ny*N + nx, dir } });
}
}
}
int main(){
int door[2][2];
int dcnt = 0;
scanf("%d", &N);
for (int n = 0; n < N; n++)
scanf("%s", map[n]);
for (int n = 0; n < N; n++){
for (int m = 0; m < N; m++){
if (map[n][m] == '#'){
door[dcnt][0] = n;
door[dcnt++][1] = m;
}
for (int k = 0; k < 4;k++)
visit[n][m][k] = INF;
}
}
bfs(door[0][0], door[0][1], door[1][0], door[1][1]);
printf("%d\n", ans);
return 0;
}
| cs |
2. 알고스팟 (★★★☆☆)
위 문제와 마찬가지로 부순 벽의 갯수를 비교하며 최소일 경우 갱신하며 나아간다.
#include <cstdio>
#include <queue>
#include <vector>
#include <functional>
#define INF 987654321
using namespace std;
typedef pair<int, int> P;
int N, M;
char map[101][101];
int bfs(){
int dist[101][101];
int dy[] = { -1, 0, 0, 1 }, dx[] = { 0, -1, 1, 0 };
priority_queue<P, vector<P>, greater<P>> pq;
for (int n = 0; n < N; n++)
for (int m = 0; m < M; m++)
dist[n][m] = INF;
pq.push({ 0, 0 });
dist[0][0] = 0;
while (!pq.empty()){
int block = pq.top().first;
int y = pq.top().second / M, x = pq.top().second % M;
pq.pop();
for (int i = 0; i < 4; i++){
int ny = y + dy[i], nx = x + dx[i];
if (ny < 0 || ny >= N || nx < 0 || nx >= M) continue;
if (map[ny][nx] == '1'){
if (dist[ny][nx] > block + 1){
dist[ny][nx] = block + 1;
pq.push({ block + 1, ny*M + nx });
}
}
else{
if (dist[ny][nx] > block){
dist[ny][nx] = block;
pq.push({ block, ny*M + nx });
}
}
}
}
return dist[N - 1][M - 1];
}
int main(){
scanf("%d%d", &M, &N);
for (int n = 0; n < N; n++)
scanf("%s", map[n]);
printf("%d\n", bfs());
return 0;
}
| cs |
3. 집배원 한상덕 (★★★★☆)
어려웠다.
고도의 최저치를 기준으로 삼고 점차 증가시키며 모든 집을 탐색할 수 있는 경우
피로도를 갱신해준다.
피로도를 갱신해준다.
#include <cstdio>
#include <queue>
#include <vector>
#include <functional>
#include <algorithm>
#define INF 987654321
using namespace std;
typedef pair<int, int> P;
int N;
char map[51][51];
int tire[51][51];
vector<int> vec;
int di(int sy,int sx, int small){
int dy[8] = { -1, 0, 0, 1, -1, -1, 1, 1 }, dx[8] = { 0, 1, -1, 0, 1, -1, 1, -1 };
int visit[51][51] = { 0 };
priority_queue<P,vector<P>, greater<P> > pq;
int ans = 0;
pq.push({tire[sy][sx] ,sy * N + sx});
while (!pq.empty()){
int dist = pq.top().first;
int y = pq.top().second / N, x = pq.top().second % N;
if (map[y][x] == 'K')
ans = max(ans, dist);
pq.pop();
if (visit[y][x]) continue;
visit[y][x] = 1;
for (int i = 0; i < 8; i++){
int ny = y + dy[i], nx = x + dx[i];
int next;
if (ny < 0 || ny >= N || nx < 0 || nx >= N) continue;
if (!visit[ny][nx] && tire[ny][nx] >= small){
next = max(tire[ny][nx], dist);
pq.push(make_pair(next, ny*N + nx));
}
}
}
for (int n = 0; n < N; n++){
for (int m = 0; m < N; m++){
if (map[n][m] == 'K' && visit[n][m] == 0)
return INF;
}
}
return ans;
}
int main(){
int sy, sx;
scanf("%d", &N);
for (int n = 0; n < N; n++)
scanf("%s", map[n]);
for (int n = 0; n < N; n++){
for (int m = 0; m < N; m++){
scanf("%d", &tire[n][m]);
vec.push_back(tire[n][m]);
if (map[n][m] == 'P'){
sy = n;
sx = m;
}
}
}
sort(vec.begin(), vec.end());
vec.erase(unique(vec.begin(), vec.end()), vec.end());
int ans = INF;
for (int i = 0; i < vec.size() && vec[i] <= tire[sy][sx]; i++)
ans = min(ans, di(sy, sx, vec[i]) - vec[i]);
printf("%d\n", ans);
return 0;
}
| cs |
4. 치~즈 (★★☆☆☆)
범위가 꽤 크다. (1000*1000)
재재새가 먹은 치즈의 정보를 bitmask로 저장할 수 있다.
방문배열을 먹은 치즈정보까지 포함해서 선언하면 런타임 에러가 발생한다. ( 1000*1000* 511 )
그러므로 이중 queue를 사용해서 처음 queue에는 재재새가 치즈를 먹을 수 있는 경우일때 삽입하고
두번째 queue에는 재재새가 치즈를 먹지않고 이동하거나 그냥 이동하는 경우에 삽입해준다.
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
typedef pair<int, int> MP;
typedef pair<MP, int> MT;
#define mp(a,b) make_pair(a,b)
#define mt(a,b,c) mp(mp(a,b),c)
struct Bird{
int y, x, info;
int skill, cnt;
Bird(int yy, int xx, int ii, int ss, int cc) :y(yy), x(xx), info(ii), skill(ss), cnt(cc){}
};
bool operator<(const Bird a, const Bird b){
return a.cnt > b.cnt;
}
int N, M, C;
bool visit[1001][1001];
char map[1001][1001];
int bfs(Bird &bird){
int dy[] = { -1, 0, 0, 1 }, dx[] = { 0, 1, -1, 0 };
priority_queue <Bird> pq;
queue<Bird> q;
pq.push(bird);
while (!pq.empty()){
Bird b = pq.top();
pq.pop();
if (b.info == (1 << C) - 1) return b.cnt;
for (int n = 0; n < N; n++)
for (int m = 0; m < M; m++)
visit[n][m] = false;
q.push(b);
visit[b.y][b.x] = true;
while (!q.empty()){
Bird here = q.front();
q.pop();
for (int i = 0; i < 4; i++){
int y = here.y + dy[i], x = here.x + dx[i];
Bird next = Bird(y, x, here.info, here.skill, here.cnt + 1);
if (y < 0 || y >= N || x < 0 || x >= M || visit[y][x] || map[y][x] == 'X') continue;
if (map[y][x] == '.'){
q.push(next);
visit[y][x] = true;
}
else{
int cheeze = map[y][x] - '0';
if (here.skill >= cheeze){ //치즈를 얻을 수 있다면
if ((here.info & (1 << (cheeze - 1))) > 0){ //이미 먹은 치즈라면
q.push(next); //지나감
visit[y][x] = true;
}
else{
visit[y][x] = true;
pq.push(Bird(y, x, here.info | (1 << (cheeze - 1)), here.skill + 1, here.cnt + 1));
}
}
else{ //못얻는다면
q.push(next);
visit[y][x] = true; //지나감
}
}
}
}
}
return -1;
}
int main(){
Bird bird(0, 0, 0, 1, 0);
scanf("%d%d%d", &N, &M, &C);
for (int n = 0; n < N; n++){
for (int m = 0; m < M; m++){
scanf(" %1c", &map[n][m]);
if (map[n][m] == 'S') bird.y = n, bird.x = m;
}
}
printf("%d\n",bfs(bird));
return 0;
}
| cs |
5. 열쇠
열쇠는 소문자 알파벳, 문은 대문자 알파벳으로 구성되며 열쇠가 있으면 문을 딸 수 있다.
최대한 얻을 수 있는 문서 개수를 구하는 문제이다.
열쇠를 획득하거나 문서를 얻을 수 있을 때 그 지역을 빈공간으로 만들고 bfs를 계속 돌려주었다.
열쇠를 획득했을 때는 그 열쇠로 딸 수 있는 모든 문을 열어주었다.
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
int N, M;
int ans;
char map[101][101];
bool visit[101][101];
int dy[] = { -1,0,0,1 };
int dx[] = { 0,1,-1,0 };
vector<char> key;
bool check(int y, int x) {
if (y < 0 || y >= N || x < 0 || x >= M || visit[y][x]) return true;
return false;
}
int save(queue<int> &q, int y, int x) {
int ret = 0;
if (map[y][x] == '.' && !visit[y][x]) {
q.push(y*M + x), visit[y][x] = true;
}
else if (('a' <= map[y][x] && map[y][x] <= 'z') || (map[y][x] == '$')) {
ret |= 1;
if (map[y][x] != '$') key.push_back(map[y][x]);
else ans++;
map[y][x] = '.';
}
return ret;
}
int bfs() {
memset(visit, false, sizeof visit);
queue<int> q;
int flag = 0;
for (int m = 0;m < M;m++) {
flag |= save(q, 0, m);
flag |= save(q, N - 1, m);
}
for (int n = 1;n < N - 1;n++) {
flag |= save(q, n, 0);
flag |= save(q, n, M - 1);
}
if (flag) return true;
while (!q.empty()) {
int y = q.front() / M, x = q.front() % M;
q.pop();
for (int i = 0;i < 4;i++) {
int ny = y + dy[i], nx = x + dx[i];
if (check(ny, nx)) continue;
if (map[ny][nx] == '.' || ('a' <= map[ny][nx] && map[ny][nx] <= 'z' ) || map[ny][nx] == '$') {
if (map[ny][nx] != '.') {
flag = true;
if ('a' <= map[ny][nx] && map[ny][nx] <= 'z') key.push_back(map[ny][nx]);
else ans++;
map[ny][nx] = '.';
}
visit[ny][nx] = true;
q.push(ny*M + nx);
}
}
}
return flag;
}
void erase() {
for (int n = 0;n < N;n++) {
for (int m = 0;m < M;m++) {
if ('A' <= map[n][m] && map[n][m] <= 'Z') {
for (auto &k : key) {
if (map[n][m] == k - 'a' + 'A') {
map[n][m] = '.';
break;
}
}
}
}
}
key.clear();
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
char K[33];
ans = 0;
key.clear();
scanf("%d%d", &N, &M);
for (int n = 0;n < N;n++) scanf("%s", &map[n]);
scanf("%s", &K);
if (K[0] != '0') {
int len = (int)strlen(K);
for (int n = 0;n < N;n++) {
for (int m = 0;m < M;m++) {
if ('A' <= map[n][m] && map[n][m] <= 'Z') {
for (int k = 0;k < len;k++) {
if (map[n][m] == K[k] - 'a' + 'A') {
map[n][m] = '.';
break;
}
}
}
}
}
}
while (bfs()) {
erase();
}
printf("%d\n", ans);
}
return 0;
}
| cs |
댓글 없음:
댓글 쓰기