[백준 20056] 마법사 상어와 파이어볼 (C++)

A. 문제설명

www.acmicpc.net/problem/20056

20056번: 마법사 상어와 파이어볼

 

문제에 대한 자세한 설명은 링크 참조

 

1. N*N 크기의 배열에서 마법사 상어가 파이어볼을 발사

2. 각 파이어볼은 위치(r,c), 질량 m, 방향 d, 속력 s가 주어짐

3. 격자의 행과 열은 1번부터 N번까지 번호가 매겨져 있고, 1번 행은 N번과 연결되어 있고, 1번 열은 N번 열과 연결되어 있음

4. 파이어볼의 방향은 인접 8방향으로 이루어짐

5. 마법사가 파이어볼에게 이동을 명령하면 아래와 같은 일들이 일어남

1. 모든 파이어볼이 자신의 방향 di로 속력 si칸 만큼 이동한다.
   ㆍ 이동하는 중에는 같은 칸에 여러 개의 파이어볼이 있을 수도 있다.
2. 이동이 모두 끝난 뒤, 2개 이상의 파이어볼이 있는 칸에서는 다음과 같은 일이 일어난다.
   1. 같은 칸에 있는 파이어볼은 모두 하나로 합쳐진다.
   2. 파이어볼은 4개의 파이어볼로 나누어진다.
   3. 나누어진 파이어볼의 질량, 속력, 방향은 다음과 같다.
      ㆍ 질량은 ⌊(합쳐진 파이어볼 질량의 합)/5⌋이다.
      ㆍ 속력은 ⌊(합쳐진 파이어볼 속력의 합)/(합쳐진 파이어볼의 개수)⌋이다.
      ㆍ 합쳐지는 파이어볼의 방향이 모두 홀수이거나 모두 짝수이면, 방향은 0, 2, 4, 6이 되고, 그렇지 않으면 1, 3, 5, 7이 된다.
   4. 질량이 0인 파이어볼은 소멸되어 없어진다.

6. 이동이 K번 일어난 후, 남은 파이어볼들의 총 질량의 합을 구하라

 

B. 접근법

시뮬레이션

 

문제 조건 자체의 이해와 독해를 잘하고 그대로 구현하면 되는 시뮬레이션 문제이다. 다만, 문제에서 헷갈리게하는 함정들이 더럿 존재하는데, 그 부분들을 먼저 짚고 넘어가보자.

 

1. 문제의 3번 조건

격자의 행과 열은 1번부터 N번까지 번호가 매겨져 있고, 1번 행은 N번과 연결되어 있고, 1번 열은 N번 열과 연결되어 있음

이 말인 즉슨, 파이어볼이 이동하여 배열의 범위 밖을 나가게될 경우, 1번에서 바깥으로 이동시, N번째로, N번에서 바깥으로 이동시 1번으로 이동한다는 것이다.

 

2. 파이어볼이 여러개일 때 합치고 나누어지기

문제의 5번 조건에서처럼, 파이어볼이 여러개일 때 이들을 합치고 새로 나누어야 한다. 나누는 과정에서 다시 이동하지 않기 때문에 일단 나누어서 새로운 객체로만 만들어 놓고, 벡터에 추가하였다.

 

위 두가지 조건에 유의하여, fVec 벡터를 이용한 파이어볼 정보 추가, arr 배열내 엔트리 안 벡터에 파이어볼 추가하여 이동하도록 구현하였다.

 

C. 풀이

1. fVec내 파이어볼들이 들어갈 다음 위치를 arr 엔트리 내 벡터에 삽입

2. 모든 파이어볼들을 arr에 삽입한 후, arr에서 각 파이어볼들을 로직에 따라 합치고 나눔

3. 새로 이동한 파이어볼의 좌표를 업데이트

4. 파이어볼이 한개인 경우 tmpVec에 그냥 바로 삽입

5. 파이어볼이 두개 이상일 경우, arr내 모든 파이어볼들을 합치고 나눔

6. 새로 나누어진 파이어볼들을 포함하여 새로 fVec을 업데이트

 

D. 내 코드

ㅇ