(BOJ 20056 마법사 상어와 파이어볼) 자료 구조, 대각선 움직임

[틀리거나 꼬인 부분]

1. 자료구조 정하는데 40분 고민

(격자 칸이 있는데, 각 칸에 여러 개수의 파이어볼을 한꺼번에 저장하는 방법?)

 

map 활용, 3차원 fireball 배열 (2차원 각 격자가 fireball 배열이 되도록), 방향에 따라 2차원 격자를 8차원으로 분리

각 자료구조 TLE 따지다가 시간 다 감.

 

 

2. 대각선 이동 구현 실패
(대각선 방향 움직임 주기 구하려다가 집중력 고갈)

goldenriver42.tistory.com/74?category=943305

 

 

---

[새로 배운 점]

 

blog.naver.com/jinhan814/222181810566

[BOJ] 20056번 - 마법사 상어와 파이어볼

 

배울점 1. 자료구조 짜임새

 

평상시에는 (전역 변수) vector<fireball> fb_info에 파이어볼 정보를 다 저장. 

 

move 함수 호출시마다

(로컬 변수) vector<fireball> board[50][50]

라는 2차원 배열 (각 칸이 파이어볼 '벡터'인) 만들어서, fb_info에 있는 파이어볼이 움직인 후의 위치를 다 기록.

 

각 칸을 돌면서, O(N^2), size >= 2인 배열인 경우 파이어볼을 다 합쳐서, 배열 초기화 후 같은 배열에 저장

 

> 교훈 : 이런 복잡한 류의 시뮬레이션 문제는 어지간히 복잡한 자료구조가 아닌 이상 TLE는 걱정할 필요 없다.
최대한 명료한 풀이가 짱이다 (ex. 한 칸에 파이어볼 여러 개 저장해야 할때 = 각 칸이 배열이 되도록)

 

2. 대각선 이동 = x, y로 쪼개서 생각하면, 결국 N으로 나눈 나머지 값이 답임

goldenriver42.tistory.com/28?category=943305 에 정리함.

나머지를 구한다는 건, N보다 작아질 때 까지 N을 반복해서 빼는 것과 같다는 식으로 생각하면 편함
    + 움직이는 방향에 따라 최종 좌표가 -가 되는 경우도 있으므로, N*1000 을 더해줘서 무조건 양수가 되도록 처리
(Q. 왜 1000이냐 > spd 최대가 1000이라 최대 -1000까지 움직이므로, 충분한 N의 배수 값을 더해줘서 양수처리;
N의 배수 값은 아무리 더해도 나중에 나머지 연산 % N 하면 다 사라지므로 ㄱㅊ)

 

3. parity( dir&1 )로 짝짝 홀홀 / 홀짝 구분 ( ^ parity)

 

goldenriver42.tistory.com/78?category=943305 에 정리함

 

 

---

각 원자 객체들을 이동시켜야 하고, 동일 위치에 여러 객체가 겹칠 수 있다는 시뮬레이션 유형 정리

 

마법사 상어와 파이어볼 식 풀이

* 매 시뮬마다 vector<Fireball> board[50][50] 2개 선언함 (크기가 작아서 충분 & 파이어볼 split 때문에 2개 필요)

배열 v에 살아있는 객체 저장 
→ 이동 후 board에 기록 (이때, int board[N][N]이 아니라 vi board[N][N]이라, 여러 개 들어가기 가능)
→ board 전체 탐색 O(N)
v.clear() 후, 살아 있는 객체 다시 배열 v에 넣기; 만약 한 칸에 여러 개 있으면 합쳐서 넣기

---

원자 소멸 시뮬레이션 식 풀이

int board[4001][4001] 사용 (global로 한번만 선언; 크기가 커서

배열 v에 살아있는 원자 저장
→ 이동 후 (실제 객체 x, y 좌표 업데이트) board에 자신의 에너지 더함;
→ 다시 배열 돌면서 원자가 이동한 위치 board에서 체크; 
board에 있는 에너지가 원자 자신의 에너지보다 클 경우, 여러 원자가 합쳐진 것으로 간주

살아있는 원자들은 배열에 다시 넣기, 여러 원자 합쳐져 있으면 합쳐서 넣기
동시에 board에 적힌 에너지 지워서 board 재활용
(tmp 배열 만들어서 기존 배열을 복사한 후, board 지우고 살아있는 놈만 다시 clear한 v에 복사)


둘의 차이점?
board 매번 새로 선언 vs 재활용 (크기가 커서 새로 선언에 너무 오래 걸림)

 

★ 핵심 포인트  
- 객체들의 움직임 구현 
→ 배열에 객체들 저장해놓고, 움직인 후에야 board에 표시
(단순히 board만 써서 움직임 표현하면, 이동 후 위치에 아직 이동하지 않은 다른 객체 있을 수도 있어서 안됨)

- 같은 칸에서 중첩돼서 합쳐지는 객체들
→ 각 칸을 벡터같은 container로 선언해서 실제로 여러 객체를 쌓던지 (vi board[N][N]),
아니면 저장되는 값이 변화했음을 파악해서 여러 객체가 합쳐졌음을 파악

 

 

추가로 비슷한 문제들 

SWEA 2382 미생물 격리