백준 11952번 좀비

🔒문제 url

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

🔑알고리즘

1. infect 배열에 점령당한 도시를 표시한다. 이 도시에서는 숙박할 수 없다.
2. infect 배열을 순회하며, BFS를 통해 위험한 도시를 표시한다.
   이때 숙박비를 나타낸 배열 cost의 값은 $q$가 된다.
   이외 지역, 즉 안전한 도시의 cost 값은 $p$가 된다.
3. 다익스트라를 통해 $N$번 도시에 도달하기까지의 최소 숙박비용을 계산한다.
   1번 도시와 $N$번 도시에서는 숙박하지 않으므로, cost 값을 0으로 설정한다.

• 총 숙박비용이 int 범위를 넘어갈 수 있으므로,long long을 사용한다.

🐾부분 코드

int n,m,k,s;
typedef long long ll;
ll p,q;
bool infect[100001];//점령당한 도시
typedef pair<ll,ll> pll;
vector<ll> graph[100001];

ll cost[100001];//각 도시의 숙박비용
int visited[100001];//for BFS 
ll dist[100001];//각 도시로 도달하기까지의 최소 숙박비용

<변수 선언>

void INPUT()
{
	IAMFAST
	cin >> n >> m >> k >> s;
	cin >> p >> q;
	for(int i = 0; i < k; i++)
	{
		int city; cin >> city;
		infect[city] = true;
	}
	for(int i = 0; i < m; i++)
	{
		int a,b; cin >> a >> b;
		graph[a].emplace_back(b);
		graph[b].emplace_back(a);
	}
}

<입력 함수>
bool type의 infect 배열에 점령당한 도시를 표시한다.
그래프의 간선은 양방향이므로 $a$와 $b$를 서로 연결한다.

void BFS(int start)
{
	fill(visited+1,visited+1+n,-1);
	queue<int> Q;
	Q.push(start);
	visited[start] = 0;
	cost[start] = 0;

	while(!Q.empty())
	{
		int now = Q.front();
		Q.pop();

		if(visited[now] == s) continue;

		for(int i = 0; i < graph[now].size(); i++)
		{
			int next = graph[now][i];
			if(visited[next] > 0) continue;

			visited[next] = visited[now] + 1;
			cost[next] = q;
			Q.push(next);
		}
	}
}

<BFS 함수 : 위험한 도시의 숙박 비용 설정>
점령당한 도시 start를 기준으로 거리가 $S$이하의 도시의 cost 값을 $q$로 지정한다.
cost는 모두 $p$로 초기화된 상태에서 BFS를 진행한다.

void ijk()
{
	fill(dist+1,dist+1+n,LONG_LONG_MAX);
	priority_queue<pll> pq;
	pq.push({0,1});
	dist[1] = 0;

	while(!pq.empty())
	{
		int now = pq.top().second;
		ll d1 = -pq.top().first;
		pq.pop();
		
		if(now == n) return;

		for(int i = 0; i < graph[now].size(); i++)
		{
			int next = graph[now][i];
			ll d2 = cost[next];

			//점령당한 도시에서는 숙박 불가	
			if(infect[next]) continue;
			if(d1 + d2 >= dist[next]) continue;

			dist[next] = d1 + d2;
			pq.push({-dist[next],next});
		}
	}
}

<다익스트라 함수>
dist의 모든 값을 LONG_LONG_MAX로 초기화한 뒤 진행한다.
$N$번 도시에 최솟값이 결정되면(pop 될때) 함수를 종료한다.

🪄전체 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
#define IAMFAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

int n,m,k,s;
typedef long long ll;
ll p,q;
bool infect[100001];
typedef pair<ll,ll> pll;
vector<ll> graph[100001];

ll cost[100001];
int visited[100001];
ll dist[100001];

void INPUT()
{
	IAMFAST
	cin >> n >> m >> k >> s;
	cin >> p >> q;
	for(int i = 0; i < k; i++)
	{
		int city; cin >> city;
		infect[city] = true;
	}
	for(int i = 0; i < m; i++)
	{
		int a,b; cin >> a >> b;
		graph[a].emplace_back(b);
		graph[b].emplace_back(a);
	}
}

void BFS(int start)
{
	fill(visited+1,visited+1+n,-1);
	queue<int> Q;
	Q.push(start);
	visited[start] = 0;
	cost[start] = 0;

	while(!Q.empty())
	{
		int now = Q.front();
		Q.pop();

		if(visited[now] == s) continue;

		for(int i = 0; i < graph[now].size(); i++)
		{
			int next = graph[now][i];
			if(visited[next] > 0) continue;

			visited[next] = visited[now] + 1;
			cost[next] = q;
			Q.push(next);
		}
	}
}

void ijk()
{
	fill(dist+1,dist+1+n,LONG_LONG_MAX);
	priority_queue<pll> pq;
	pq.push({0,1});
	dist[1] = 0;

	while(!pq.empty())
	{
		int now = pq.top().second;
		ll d1 = -pq.top().first;
		pq.pop();
		
		if(now == n) return;

		for(int i = 0; i < graph[now].size(); i++)
		{
			int next = graph[now][i];
			ll d2 = cost[next];

			if(infect[next]) continue;
			if(d1 + d2 >= dist[next]) continue;

			dist[next] = d1 + d2;
			pq.push({-dist[next],next});
		}
	}
}

void SOLVE()
{
	fill(cost+1,cost+1+n,p);
	for(int i = 1; i <= n; i++)
		if(infect[i]) BFS(i);
	cost[n] = 0;

	ijk();
	cout << dist[n];
}

int main()
{
	INPUT();
	SOLVE();
}

🥇문제 후기

진짜.... 욕을 한바가지 쏟아내며 3시간 디버깅한 문제....
알고리즘은 처음부터 정확하게 접근했다. 애초에 Gold2 받기에는 쉬운 문제니까..
근데 dist를 INT_MAX가 아니라 LONG_LONG_MAX로 초기화했어야하는 걸.....ㅎㅎ😁
굉장히 분하고 힘들었지만, 값진 경험을 했다..!다음 페이지도 있음 주의