반응형
출처
https://swexpertacademy.com/main/solvingProblem/solvingProblem.do
SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
1. 구조체 배열 초기화는 for문으로 값을 입력시켜서 초기화 시키면 시간이 2배 증가.
따라서 memset사용.
2. 아이디어
-기본적으로 BFS로 구현함.
-음수좌표 양수로 치환.
-터지는 경우
어떤 지점에 도착했을 때, 같은 시점에 누군가가 도착한 경우 혹은 같은 시점에 그지점이 터져있는 경우
current+1(이동한 후의 current) 와 해당 지점의 current가 일치 할 때 폭파, 폭파되었다는 check를 심어줌.
그리고 그위치는 비움.
어떤 지점에 도착했을 때, 누군가가 머무르고 있는데 그 누군가가 자신의 방향으로 다가오는 경우
visit가 존재하지만 current는 현재 자신과 같음.
다가오는 상대도 죽이고, 자신이 이동할 그 위치도 비움.
-안터지는 경우
아무도 방문하지 않은 지점
누군가 있지만 자신에게 오는 경우도 아니고 터져있는 경우도 아니고 같은 시점에 들어오는 경우도 아닐때.
이때는 현재의 자기 위치를 비우고 그 위치로 옮기는데 자기가 옮기는 동시에 누군가가 자기자리에 들어왔을 수도 있음.
따라서 비울때는 현재 자신의 위치의 인덱스가 자신인지 확인 해야 함.
#include<iostream>
#include<queue>
#include<string.h>
using namespace std;
struct Node{
int current;
int index;
bool visited;
bool check;
};
struct Index{
int x;
int y;
int dir;
int cost;
int index;
int current;
bool alive;
};
Node visit[2001][2001];
Index arr[1001];
int main(void)
{
int test_case;
cin >> test_case;
for(int tc = 1; tc<= test_case; tc++)
{
memset(visit,0,sizeof(visit));
int N;
cin >> N;
queue<Index> que;
int result = 0;
for(int i = 1; i<=N; i++)
{
int x,y,dir,cost;
cin >> x >> y >> dir >> cost;
arr[i] = {x+1000,y+1000,dir,cost,i,0,true};
que.push(arr[i]);
visit[y+1000][x+1000] = {0,i,true};
}
while(!que.empty())
{
int y = que.front().y;
int x = que.front().x;
int dir = que.front().dir;
int cost = que.front().cost;
int index = que.front().index;
int current = que.front().current;
que.pop();
if(N == 0)
{
break;
}
if(!arr[index].alive)
continue;
if(dir == 0)
{
if(y+1 > 2000)
{
N--;
if(visit[y][x].index == index)
visit[y][x].visited = false;
arr[index].alive = false;
}
else
{
if(visit[y+1][x].visited)
{
if(visit[y+1][x].current == current+1)
{
if(visit[y][x].index == index)
visit[y][x].visited = false;
if(arr[visit[y+1][x].index].alive)
{
arr[visit[y+1][x].index].alive = false;
N--;
result += arr[visit[y+1][x].index].cost;
}
arr[index].alive = false;
N--;
visit[y+1][x].index = index;
visit[y+1][x].check = true;
result += arr[index].cost;
}
else if(visit[y+1][x].current == current )
{
if(visit[y][x].index == index)
visit[y][x].visited = false;
if(arr[visit[y+1][x].index].dir == 1 && !visit[y+1][x].check)
{
arr[index].alive = false;
result += arr[index].cost;
N--;
arr[visit[y+1][x].index].alive = false;
result += arr[visit[y+1][x].index].cost;
N--;
visit[y+1][x].visited = false;
}
else
{
visit[y][x].visited = false;
visit[y+1][x].visited = true;
visit[y+1][x].index = index;
visit[y+1][x].current = current+1;
arr[index].current = current+1;
que.push({x,y+1,dir,cost,index,current+1,true});
}
}
else
{
if(visit[y][x].index == index)
visit[y][x].visited = false;
visit[y+1][x].visited = true;
visit[y+1][x].index = index;
visit[y+1][x].current = current+1;
arr[index].current = current+1;
que.push({x,y+1,dir,cost,index,current+1,true});
}
}
else
{
if(visit[y][x].index == index)
visit[y][x].visited = false;
visit[y+1][x].visited = true;
visit[y+1][x].index = index;
visit[y+1][x].current = current+1;
arr[index].current = current+1;
que.push({x,y+1,dir,cost,index,current+1,true});
}
}
}
else if(dir == 1)
{
if(y-1 < 0)
{
N--;
if(visit[y][x].index == index)
visit[y][x].visited = false;
arr[index].alive = false;
}
else
{
if(visit[y-1][x].visited)
{
if(visit[y-1][x].current == current+1)
{
if(visit[y][x].index == index)
visit[y][x].visited = false;
if(arr[visit[y-1][x].index].alive)
{
arr[visit[y-1][x].index].alive = false;
N--;
result += arr[visit[y-1][x].index].cost;
}
arr[index].alive = false;
N--;
visit[y-1][x].index = index;
visit[y-1][x].check = true;
result += arr[index].cost;
}
else if(visit[y-1][x].current == current)
{
if(visit[y][x].index == index)
visit[y][x].visited = false;
if(arr[visit[y-1][x].index].dir == 0 && !visit[y-1][x].check)
{
arr[index].alive = false;
result += arr[index].cost;
N--;
arr[visit[y-1][x].index].alive = false;
result += arr[visit[y-1][x].index].cost;
N--;
visit[y-1][x].visited = false;
}
else
{
if(visit[y][x].index == index)
visit[y][x].visited = false;
visit[y-1][x].visited = true;
visit[y-1][x].index = index;
visit[y-1][x].current = current+1;
arr[index].current = current+1;
que.push({x,y-1,dir,cost,index,current+1,true});
}
}
else
{
if(visit[y][x].index == index)
visit[y][x].visited = false;
visit[y-1][x].visited = true;
visit[y-1][x].index = index;
visit[y-1][x].current = current+1;
arr[index].current = current+1;
que.push({x,y-1,dir,cost,index,current+1,true});
}
}
else
{
if(visit[y][x].index == index)
visit[y][x].visited = false;
visit[y-1][x].visited = true;
visit[y-1][x].index = index;
visit[y-1][x].current = current+1;
arr[index].current = current+1;
que.push({x,y-1,dir,cost,index,current+1,true});
}
}
}
else if(dir == 2)
{
if(x-1 < 0)
{
N--;
if(visit[y][x].index == index)
visit[y][x].visited = false;
arr[index].alive = false;
}
else
{
if(visit[y][x-1].visited)
{
if(visit[y][x-1].current == current+1)
{
if(visit[y][x].index == index)
visit[y][x].visited = false;
if(arr[visit[y][x-1].index].alive)
{
arr[visit[y][x-1].index].alive = false;
N--;
result += arr[visit[y][x-1].index].cost;
}
arr[index].alive = false;
N--;
visit[y][x-1].index = index;
visit[y][x-1].check = true;
result += arr[index].cost;
}
else if(visit[y][x-1].current == current)
{
if(visit[y][x].index == index)
visit[y][x].visited = false;
if(arr[visit[y][x-1].index].dir == 3 && !visit[y][x-1].check)
{
arr[index].alive = false;
result += arr[index].cost;
N--;
arr[visit[y][x-1].index].alive = false;
result += arr[visit[y][x-1].index].cost;
N--;
visit[y][x-1].visited = false;
}
else
{
if(visit[y][x].index == index)
visit[y][x].visited = false;
visit[y][x-1].visited = true;
visit[y][x-1].index = index;
visit[y][x-1].current = current+1;
arr[index].current = current+1;
que.push({x-1,y,dir,cost,index,current+1,true});
}
}
else
{
if(visit[y][x].index == index)
visit[y][x].visited = false;
visit[y][x-1].visited = true;
visit[y][x-1].index = index;
visit[y][x-1].current = current+1;
arr[index].current = current+1;
que.push({x-1,y,dir,cost,index,current+1,true});
}
}
else
{
if(visit[y][x].index == index)
visit[y][x].visited = false;
visit[y][x-1].visited = true;
visit[y][x-1].index = index;
visit[y][x-1].current = current+1;
arr[index].current = current+1;
que.push({x-1,y,dir,cost,index,current+1,true});
}
}
}
else if(dir == 3)
{
if(x+1 > 2000)
{
N--;
if(visit[y][x].index == index)
visit[y][x].visited = false;
arr[index].alive = false;
}
else
{
if(visit[y][x+1].visited)
{
if(visit[y][x+1].current == current+1)
{
if(visit[y][x].index == index)
visit[y][x].visited = false;
if(arr[visit[y][x+1].index].alive)
{
arr[visit[y][x+1].index].alive = false;
N--;
result += arr[visit[y][x+1].index].cost;
}
arr[index].alive = false;
N--;
visit[y][x+1].index = index;
visit[y][x+1].check = true;
result += arr[index].cost;
}
else if(visit[y][x+1].current == current)
{
if(visit[y][x].index == index)
visit[y][x].visited = false;
if(arr[visit[y][x+1].index].dir == 2 && !visit[y][x+1].check)
{
arr[index].alive = false;
result += arr[index].cost;
N--;
arr[visit[y][x+1].index].alive = false;
result += arr[visit[y][x+1].index].cost;
N--;
visit[y][x+1].visited = false;
}
else
{
if(visit[y][x].index == index)
visit[y][x].visited = false;
visit[y][x+1].visited = true;
visit[y][x+1].index = index;
visit[y][x+1].current = current+1;
arr[index].current = current+1;
que.push({x+1,y,dir,cost,index,current+1,true});
}
}
else
{
if(visit[y][x].index == index)
visit[y][x].visited = false;
visit[y][x+1].visited = true;
visit[y][x+1].index = index;
visit[y][x+1].current = current+1;
arr[index].current = current+1;
que.push({x+1,y,dir,cost,index,current+1,true});
}
}
else
{
if(visit[y][x].index == index)
visit[y][x].visited = false;
visit[y][x+1].visited = true;
visit[y][x+1].index = index;
visit[y][x+1].current = current+1;
arr[index].current = current+1;
que.push({x+1,y,dir,cost,index,current+1,true});
}
}
}
}
cout<<"#"<<tc<<" "<<result<<endl;
}
return 0;
}반응형
'Algorithm' 카테고리의 다른 글
| 백준 9933번 민균이의 비밀번호 (0) | 2020.01.01 |
|---|---|
| 백준 1764번 듣보잡 (0) | 2020.01.01 |
| 7673. 영이는 영이 시져시져! (0) | 2019.12.29 |
| 1247. [S/W 문제해결 응용] 3일차 - 최적 경로 (0) | 2019.12.28 |
| 1953. [모의 SW 역량테스트] 탈주범 검거 (0) | 2019.12.25 |