12869번: 뮤탈리스크
1, 3, 2 순서대로 공격을 하면, 남은 체력은 (12-9, 10-1, 4-3) = (3, 9, 1)이다. 2, 1, 3 순서대로 공격을 하면, 남은 체력은 (0, 0, 0)이다.
www.acmicpc.net
/*
* bfs algorithm
* 1.초기화
* 2.종료조건
* 3.next
* 4.next 방문체크
* 5.visit[next] 갱신
*/
*핵심로직
1. visit[체력][체력][체력] = 최단거리(공격횟수)
1.1 idx에 각각 체력저장.
2.v[0][0][0] 에 방문했다? -> bfs이므로 ->
최초 체력 0,0,0으로 만든애가 최단거리임. -> 출력. 끝.
#include <bits/stdc++.h>
using namespace std;
int a[3];
int n, dx[4] = { -1,0,1,0 }, dy[4] = { 0,-1,0,1 };
int visited[64][64][64];
vector<pair<int, int>> v;
int mutal[6][3] = {
{9,3,1},
{9,1,3},
{3,1,9},
{3,9,1},
{1,3,9},
{1,9,3}
};
bool in(int a, int b) {
return 0 <= a && a < n && 0 <= b && b < n;
}
/*
* tuple<int,int,int>보다
* struct로 삼변수저장.
* class는 push(1,2,3)이 안됨.
*/
struct A {
int a, b, c;
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n ;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
/*
* bfs algorithm
* 1.초기화
* 2.종료조건
* 3.next
* 4.next 방문체크
* 5.visit[next] 갱신
*/
queue<A> q;
q.push({ a[0],a[1],a[2] });
visited[a[0]][a[1]][a[2]] = 1;
while (q.size())
{
int a = q.front().a;
int b = q.front().b;
int c = q.front().c;
q.pop();
if (visited[0][0][0]) break;
for (int i = 0; i < 6; ++i)
{
int na = max(0, a - mutal[i][0]);
int nb = max(0, b - mutal[i][1]);
int nc = max(0, c - mutal[i][2]);
if (visited[na][nb][nc]) continue;
visited[na][nb][nc] = visited[a][b][c] + 1;
q.push({ na,nb,nc });
}
}
cout << visited[0][0][0]-1;
}
/*
3
12 10 4
2 */
'Algorithm > boj' 카테고리의 다른 글
백준 12851 // bfs암기, 정답 경우의수 구하기는 cnt[next]+=cnt[here] (0) | 2023.06.09 |
---|---|
백준 13913 // bfs 경로추적은 prev[next]=here (0) | 2023.06.09 |
백준 16234 인구이동 // ny,nx만처리하는 bfs / main에서 v[y][x]처리 / vector &v로 함수내 전역변수 사용 (1) | 2023.06.01 |
백준 4179 // 갈수있는지조사는 bfs visit 비교 (0) | 2023.05.31 |
백준 15686 // 조합함수암기! (0) | 2023.05.30 |