https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRFInKex8DFAUo
어려웠습니다…
우선 원자 충돌 시 반대방향에서 x.5초에서 부딪힐 경우를 고려해야 했으므로 많은 고민이 필요했습니다.
어떤 분은 곱하기 2를 해서 해결하신 분들도 계시던데 저는 주어진대로 구현했습니다.
먼저 음수는 배열을 사용하여 판단하기 힘드므로 좌표 입력시 모두 1001을 더해줬고
저 같은 경우 1.반대방향에서 충돌 시, 2. 다른 방향에서 충돌 시 이렇게 2가지 충돌을 나눠서 풀었습니다.
1.반대방향에서 충돌 시(x.5초 후 충돌)
매순간 모든 원자들이 한칸씩 이동하는데 이동하는 자리에 원자가 있을 경우, 이 원자가 방향이 반대 방향이면 x.5초 충돌로 판단했습니다.
현재원자와 비교할원자의 합이 1이거나 5이면 서로 반대방향이므로 이렇게 판단 했습니다.
먼저 반대방향 충돌을 판단 후 그다음 나머지 방향에서 충돌을 판단했습니다.
2.다른 방향에서 충돌 시
따로 nmap(next map)이라는 배열을 만들어 이동 후 좌표를 임시로 nmap에 넣어 줬습니다.
이때 다른 원자들도 마찬가지로 이동시 nmap에 넣게 되는데, 이 때 이미 nmap에 기존의 원자가 입력돼있으면
충돌로 판단했습니다. 이렇게하면 다른원자들도 충돌을 모두 판단할 수 있습니다.
이렇게 사용을 끝낸 nmap은 다시 모두 0으로 초기화하고 다음 이동때 다시 사용하게 했습니다.
이렇게 충돌을 판단하고 충돌되지않고 범위 밖으로 나간 원자들도 판단한 후, 마지막에 충돌한 원자들을 모두 더하여
결과값을 도출했습니다.
#include <iostream>
using namespace std;
struct atomInfo {
int x;
int y;
int dir;
int k;
}atom[1001];
int map[2002][2002];
int nmap[2002][2002];
int dx[] = { 0,0,-1,1 };
int dy[] = { 1,-1,0,0 };
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int test_case;
cin >> test_case;
for (int t = 1; t <= test_case; t++) {
//초기화
int n,result = 0;
int time = 0;
bool crushed[1001] = { 0, };
bool out[1001] = { 0, };
for (int i = 0; i < 2002; i++)
for (int j = 0; j < 2002; j++)
map[i][j] = 0;
//start
cin >> n;
for (int i = 1; i <= n; i++) {
int x, y, dir, k;
cin >> x >> y >> dir >> k;
atom[i].x = x + 1001;//양수로 변환
atom[i].y = y + 1001;
atom[i].dir = dir;
atom[i].k = k;
map[x + 1001][y + 1001] = i;
}
while (1) {
time++;
if (time == 2001) break;//2001을넘으면 범위를 벗어나므로
for (int i = 1; i <= n; i++) {
if (crushed[i] == true||out[i]==true) continue;//충돌했거나 범위 밖이면 패스
int x = atom[i].x;
int y = atom[i].y;
int dir = atom[i].dir;
int k = atom[i].k;
int nx = x + dx[dir];//이동후 위치(next x)
int ny = y + dy[dir];
if (nx < 0 || ny < 0 || nx >= 2002 || ny >= 2002) {
out[i] = true;//범위밖으로나간원자
continue;
}
atom[i].x = nx;//좌표이동 후 갱신
atom[i].y = ny;
map[x][y] = 0;//초기화
if (map[nx][ny] != 0) {//반대방향 충돌
int ori = map[nx][ny];
if (dir + atom[ori].dir == 1 || dir + atom[ori].dir == 5) {
crushed[i] = true;
crushed[ori] = true;
map[nx][ny] = 0;
continue;
}
}
if (nmap[nx][ny] == 0) {//충돌x
nmap[nx][ny] = i;
}
else {
//다른방향 충돌
int ori = nmap[nx][ny];
crushed[i] = true;
crushed[ori] = true;
}
}
for (int i = 1; i <= n; i++) {//이동후를 map에 다시그림
int nx = atom[i].x;
int ny = atom[i].y;
nmap[nx][ny] = 0;//nmap은 다 0으로 초기화
if (crushed[i] == false&&out[i]==false) {
map[nx][ny] = i;
}
}
}
//충돌한애들 모두 더하기
for (int i = 1; i <= n; i++) {
if (crushed[i] == true) {
result += atom[i].k;
}
}
cout << '#' << t << ' ' << result << '\n';
//end
}
}
- 나 혼자 말하고 나 혼자 듣는 말
하.. 처음 풀었는데 어려웠다. x.5초.. 고려하느라 머리 깨지는줄알았다.
다른사람들보니까 곱하기2해서 해결했던데 나도 이렇게 해볼걸..
아니다 하지만 난 메모리를 많이 줄였잖아!!ㅋㅋㅋ
후… 이렇게 겨우 해결했는데……….. 하.. 다른사람들 반례 다 넣어도
(15/50)해결돼서 아니 49도아닌 15라고?!?!!?!? 맨붕때리면서 고민했었는데
알고보니 map배열 초기화…. ㅠㅠ.. 반복문안에서 초기화해서 안해도 될줄알았는데
알고보니 마지막에 입력을 넣었던것.. 이런 한심하고 바보같은자식…
다음부턴 초기화를잘하자!!!!! 초기화!!초기화!! 잘하자!!! 아오!!