최근 추가 241029
-> 최소값? 최단 경로는 bfs를 생각하자.
반드시 visited 불변수가 따라와야만 동일한 가중치에서 최소값을 얻을 수 있다!
최근풀이 240404 틀림
: 반드시 방문처리를 해야 한다.
-> 최소값을 구해야 하기 때문에
: 방문처리 안하고 풀면 메모리 초과된다 queue 증가로 인해
- 최근 풀이 -> 다시 풀어서 맞음.
https://www.acmicpc.net/submit/12869/76338155
제출 코드
https://www.acmicpc.net/submit/12869/49493554
bfs에서의 방문 처리에 대해서
bfs 의 방문처리에 대해서
: 알고리즘 문제 해결 전략 p.881
어떻게 접근해야 할까? 240116
: 일단 확실한 거는 뮤탈리스크가 3번 공격이 가능하고,
만약 scv 3마리가 있다면, 데미지를 가할 수 있는 경우의 수는 3! , 즉 6임.
그림은 scv 인 a,b,c 에게 뮤탈이 공격을 가할 수 있는 경우의 수를 그림으로 나타낸 것이고, abc 밑의 숫자를 abc의 체력에 감산작업을 하고, 이어서
뮤탈은 연이어 공격을 하는 그림을 나타낼 수 있음.
즉 경우의 수 6가지를 동일한 가중치로 나타낼수 있음.
-
그렇다면 기존의 bfs 는 pair dir[4] = { {-1,0} {1,0} {0,-1} {0,1} }형식으로 진행했는데
여기서는 tuple 형식으로 [6] 개 만들어 놓고 진행하면 좋을 듯 함.
https://velog.io/@kwt0124/tuple-%EC%82%AC%EC%9A%A9%ED%95%A0%EB%95%8C -
이런식으로 작성할 수 있는데,,,
-
0,0,0이 될수 있는 최소값을 구하는 것인데, 어떻게 최소값을 구할지를 생각해야 함....
-> bfs로 풀기로 했기 때문에 동일한 가중치를 위해서 visited 를 사용해야 함. -
현재 문제에서 61 미만이고, scv는 총 3마리까지만 존재한다고 하니까.
visited[61][61][61] 로 나타낼 수 있음.
의문점.
어떻게 단정 지을 수 있냐???
bfs로 진행할 경우, 데미지가 음수가 아닌 이상 가중치가 낮을 수록 가장 먼저 특정한 인덱스에 접근하게 됨. 이 때 visited[][][] = value; 이런식으로 작성하게 되고 ,
value가 낮을 수록 더 졸은 것임!
큰돌님 작성하신 내용
네 맞습니다. 일단 visited에는 최단거리 배열만 들어가게 되며 먼저 채워지면 그 다음, 해당 visitied를 한 이후의 정점에서 채워지는 원소는 더 큰값이 들어오게 됩니다.
이렇게 탐색을 하기 때문에 먼저 방문한 정점이 최단거리이고 뻗어나갈수록 더 커진 값이 들어가게 됩니다.
또한 이 continue부분은 방문한 정점은 다시 방문하지 않는다라는 의미로 BFS라면 그냥 있는 로직입니다. 3차원이라고 해서 달라지지는 않습니다.
개선해야 할 점.
- 메모이제이션 배열의 크기를 넉넉하게 만들자.
언제품?
- 220910
- 220922
🙈풀이전략
1) 최대 3개의 scv 에다가 3개의 다른 데미지를 가할 수 있는 경우의 수는
3! : 6개임
2) 동일한 가중치에서 묶음의 scv에 데미지를 가한 후, 카운팅을 반복해야함.
-> bfs를 해야 함.
3) 🙈bfs이므로 체크 변수가 필요함.
-> 여기서 사용되는 변수는 최단시간에 최대 3마리의 scv를 죽일수 있는지를
알아야 함.
- 결론
: 3마리의 hp의 정보를 가지고 있는 3차원 메모이제이션 배열을 만들어서
방문처리하는 방식으로 사용했음!
주의할 점.
1번. 메모이제이션 인덱스 범위
: 이렇게 하면 안됨.
- 이유?
: 예제 3,4번에서 이미 0미만으로 떨어지는 것을 어떻게 처리할 것인가????
--> 0미만이라면, 0으로 세팅을 해야, 입력 4번을 1회만에 처리할 수 있음.
2번. 메모이제이션 배열의 크기
: 60보다 큰값으로 설정해야 함.
60으로 했더니 틀림...
62로 변경했더니 맞음.
코드
1) bfs 형식을 갖추도록 만듦
2) 상태값, 불변수 처리
: scv의 상태값을 어떻게 처리할 것인가?
가 ) check[1번 scv의 hp][2번 scv의 hp][3번 scv의 hp]
나) 해당 변수에는 최단 거리를 저장해야 함.
다) 그러다가 check[0][0][0] 에 값이 저장되면 종료!
최종 코드
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
#include <iostream>
#include <queue>
#include <algorithm>
int damage[][3]
{
{9,3,1},
{9,1,3},
{3,9,1},
{3,1,9},
{1,3,9},
{1,9,3},
};
//뭔가를 하나의 덩어리로 처리할때는 구조체를 사용
// scv의 최대 갯수는 3이므로
struct scv
{
int a[3]{0,};
};
// 진입하는 scv들의 정보를 가지고
// 9 3 1 이 동시에 먹어야 함.
// 동일한 가중치에서 감산이 이루어짐.
// bfs로 접근해야함.
// 예시
// 12 10 4 진입시
// 12의 경우, 9 , // 10의 경우 , 3 // 4 의경우 , 1
// damage 배열을 6번 먹힌 값으로 돌아 야함.
int visitied[64][64][64];
int bfs(scv &_sscv)
{
// 모든 scv의 hp정보를 이용해
// 동일한 가중치에서 처리하기 위해 큐를 만듦
queue<scv>q;
q.push(_sscv);
visitied[_sscv.a[0]][_sscv.a[1]][_sscv.a[2]] = 1;
while (!q.empty())
{
int a = q.front().a[0];
int b = q.front().a[1];
int c = q.front().a[2];
q.pop();
if (visitied[0][0][0])
break;
for (int i = 0; i < 6; ++i)
{
int na = max(0, a - damage[i][0]);
int nb = max(0, b - damage[i][1]);
int nc = max(0, c - damage[i][2]);
if (visitied[na][nb][nc]) continue;
visitied[na][nb][nc] = visitied[a][b][c] + 1;
q.push({ na, nb, nc });
}
}
return visitied[0][0][0] - 1;
}
int main()
{
int n;
cin >> n;
//벡터로 하면 안됨.
scv sscv;
for (int i = 0; i < n; ++i)
cin >> sscv.a[i];
cout << bfs(sscv);
}
