문제 링크
나는 BFS로 푼 문제이다. 시작 점이 꼭 1번 건물이 아닐 수도 있으므로 모든 건물의 정보를 입력 받는 과정에, 그 이전 단계가 있는 건물들은 시작 건물이 아니라 단정하고 시작 건물들이 가능한 건물들은 처음에 큐에 미리 넣어주고 BFS를 진행하였다.
이 문제에 함정이 있는 게, 문제는 최소 시간을 구하라고 하는데 따지고 보면 그냥 그 단계까지 누적 최고 건설 시간들만 구해주면 된다. 왜냐하면 특정 단계 건물을 짓기 위해서는 선행 건물들을 모두 지어야 하는데, 선행 건물들 중에 건설 시간이 짧은 것을 아무리 먼저 지어도 건설 시간이 긴 건물이 지어지기 전까지는 그 특정 단계의 건물을 지을 수 없기 때문이다.
이 로직 대로 코드를 짰는데, 처음에 문제를 풀 때 시간 초과가 났었다. 뭐가 문제인가 고민을 해봤더니, 초기에는 build배열에서 첫 번째 인덱스는 현재 건물, 두 번째 인덱스는 다른 건물을 인덱스로 두고, 그 배열 값이 참이면 경로가 존재한다고 하고 풀이를 진행했었다.
이 과정에서 매 루프마다 그때의 건물 배열을 1부터, n까지 전부 다 경로 검사를 진행해야 하니 시간 초과가 일어난 것이다. 그래서 일일이 해당 인덱스에 저장하는 방법을 버리고 해당 건물이 가진 경로의 개수를 path 배열 에다가 저장하고, 배열의 1 인덱스부터 다음 경로들을 저장하는 방법을 택하니 시간 초과에서 벗어났다.
밑은 위의 과정대로 작성한 코드이다.
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
//각 건물의 인덱스 0번에 건설 시간을 저장한다.
int t,build[1001][1001],isFirst[1001]={0,},value[1001],path[1001];
int x,y,n,k,w;
queue<int> q;
int bfs(){
int ret = 0;
//시작점이 가능한 것들을 전부 큐에 넣는다.
for(int i=1;i<=n;i++){
if(isFirst[i]==0){
q.push(i);
//초기 빌드의 누적 비용을 건설 비용으로 초기화한다.
value[i] = build[i][0];
}
}
//BFS를 진행한다.
while(!q.empty()){
//큐에서 인덱스를 하나씩 꺼내서, 다음 경로에서 가능한 것을 찾는다.
int p = q.front(); q.pop();
//원하는 건물에 도달하면, 최대 값을 넣어준다.
if(p==w) ret = max(ret,value[p]);
else{
for(int i=1;i<=path[p];i++){
if(build[p][i]>=1){
int a = build[p][i];
// 다음 빌드를 짓는 데에 드는 최대 비용을 구한다. 최대 비용이 안되면 enqueue 하지 않는다.
if(value[a] < value[p]+build[a][0]){
value[a] =value[p] + build[a][0];
q.push(a);
}
}
}
}
}
return ret;
}
int main(){
scanf("%d",&t);
while(t--){
//초기화//
for(int i=0; i<q.size();i++) q.pop();
memset(build,0,sizeof(build));
memset(value,0,sizeof(value));
memset(isFirst,0,sizeof(isFirst));
memset(length,0,sizeof(length));
//건물의 갯수와 건설 규칙 순서
scanf("%d %d",&n,&k);
//각 건물 0번 인덱스에 건물의 건설 시간을 저장한다.
for(int i=1;i<=n;i++)
scanf("%d",&build[i][0]);
//각 건물의 경로 초기화
for(int i=0;i<k;i++){
scanf("%d %d",&x,&y);
int a = ++path[x];
//해당 경로가 있음을 표시하기위해 1을 저장한다.
build[x][a] = y;
//또한 해당 경로가 시작점이 가능한지 아닌지도 체크를 해야된다.
isFirst[y] = 1;
}
//목표 건물
scanf("%d",&w);
printf("%d\n",bfs());
}
}
변수가 쓸대 없이 많아진 것 같아 나중에 시간을 내서 리팩토링을 해야겠단 생각이 든다.
정답률이 15%라 엄청 긴장하고 풀었는데 그 정도 까지의 문제는 아니었던 것 같다.
