원자 소멸 시뮬레이션

유튜브 영상(https://www.youtube.com/watch?v=ylQEUhuXWeY) 참고 풀이 문제를 풀 때, 문제 접근 방법, 어떤 내용을 하이라이트하고 노트테이킹하면서 유념해서 풀어야 하는지 숙지!

문제 풀기 위해 중요한 내용 노트 테이킹

  1. 애매한 1.5초 상황 : 원자 간의 거리가 홀수이기 때문이다. 그래서 이 홀수를 짝수로 만들면 좋다! => 초기 위치 좌표를 *2 해주면 된다!

  2. 좌표 범위 제한 : 문제에서 좌표 범위의 제한은 없다고 나와있지만 이것은 훼이크다. 정말 봐야하는 것은 초기위치의 범위 제한이다! 초기 위치의 범위값보다 벗어나는 좌표값이라면 이 원자는 이동을 무한히 반복해도 충돌할 일이 없다. 왜냐하면 초기 위치 범위를 벗어난다면 상하좌우 4가지 방향에서 오는 원자들과 부딪힌다는 것인데,

    원자들은 초기 위치 범위 이내에서 원직이기 때문이다!! 따라서, -1,000 <= x,y <= 1000 ➡ -2,000<=x,y<=2,000 또는 0<=x,y<=4000 (계산의 편의를 위해 양수로 바꿨다는데 굳이 양수로 까지 바꾸진 않아도 될 것 같다)

  3. 충돌 처리 : 원자들을 다 이동시킨 후, 한 곳에 2개 이상일 때 한번에 처리한다. 왜냐하면 한 턴에서 4가지 방향에서 최대 4개의 원자가 충돌할 수가 있는데, 이 때 원자 한개씩 해버리면 마지막 원자는 충돌처리에 해당되지 않기 때문이다. 따라서 원자들을 고유한 방향으로 모두 이동시킨 다음, 일괄적으로 한번에 충돌 처리해주어야 한다.

자료구조

  1. 테스트 케이스 갯수 TC

  2. 원자 갯수 N

  3. 이동 방향(UP = 0, DOWN = 1, LEFT = 2, RIGHT = 3)

  4. 충돌한 에너지 총합 E

  5. 전체 원자의 목록 List<Atom>

  6. 이동된 원자 좌표 기준🔑 으로 목록으로 관리하는 맵 : Map<Integer,List<Atom>> moveMap => 이 맵은 생각은 했었지만, 무한한 좌표범위를 응용하지 못해서 배열로 나타낼 수 없었다. 2차원 상의 어떤 객체는 2차원 배열로 그 위치를 나타낼 수 있고, 2차원 위치값은 배열의 행과 열 값을 이용하여 하나의 정수로 표현할 수 있는데 말이다. 하지만 이 코드에서처럼, 객체와 객체 타입의 리스트로 원자 정보를 저장해도, 원자의 위치를 Integer 타입으로 나타내어 저장할 수 있다. =>-2,000 ~ 2,000 또는 0 ~ 4,000 범위를 벗어나면 관리하지 않는다. 그렇기 때문에 실제 배열을 사용하지 않더라도, 4,000 x 4,000 크기의 2차원 공간, 2차원 배열 상에 원자를 나타낼 수 있다. 이 때, 행과 열 크기는 4001이 된다. 왜냐하면 -2 ~2 : -2,-1,0,1,2 = 2*2 + 1이고, 0 ~ 4,000도 4001개이기 때문에 여기서도 마찬가지로 -2,000 ~ 2,000 이 범위라면 2,000*2 +1이되는 것이다. 따라서 구하고자하는 Map의 key = 2차원 배열의 인덱스를 정수로 계산하면 atom.row*4001 + atom.col이 된다.

  7. 매 턴이 끝나고 지울 원자의 목록 : List<Atom> delList

구현 Tip

  1. 원자 클래스(Atom) 만들 때, 상하좌우 이동하는 메서드를 함께 구현

  2. 원자 이동&충돌 처리 : 이동하다가 충돌/범위 밖의 원자가 발생하면 리스트에서 삭제해야하지만, 인덱스를 조절해줘야하고, for(Atom a: list)같은 iteration for문(int i-for문 같은 인덱스가 있는 반복문이 아님)은 인덱스를 조절할 수 없기 때문에, 이러한 반복문을 돌면서 삭제를 할 수 없다. 따라서 N개의 모든 원자들을 다 이동시킨 후에 일괄적으로 충돌 처리할 것이기 때문에 이동시킨 원자들을 좌표값을 key로 하는 map에 저장해둔다!

  3. moveMap : 각 턴마다 위치별 원자 정보 저장 리스트

  4. delList : 각 턴마다 없어지는 원자들 관리 => moveMap, delList 턴마다 초기화 필요.

두번째 풀었을 때 : 오답이 나오다가 정답으로 나와서 pass했다!

배운점 : 리팩토링으로 코드 간결성과 가독성을 높일 수 있다! ① Atom 클래스를 만들 때, Atom이 하는 행위(이동)를 함께 구현한다! 그러면 a.move(); 단 한줄로 코드가 깔끔해진다! 간결성++ ex) 리모콘 객체를 만들 때, 볼륨 조절, 채널 이동 같은 메서드를 함께 구현하는 것과 같은 이치이다! ② 상하좌우 또는 새로운 게임2에서 처럼 어떤 숫자값이 의미를 가질 때, 전역변수로 그 의미와 맞는 이름을 대문자로 선언해주면 코드의 가독성이 올라간다! ③ 반복을 종료하는 조건은 반복문 아래가 아니라 반복문 초반 부분에 위치시키기!⭐️ ④ 컬렉션 함수 clear()로 객체 초기화 매 이동(반복문 텀)마다 이동한 위치에 따른 moveMap과 delList를 초기화해주어야한다. 이 때 객체를 새로 생성하는 것으로 했지만, 이렇게 되면 메모리에 불필요하게 계속해서 객체가 생성될 것이다. 그러므로 객체는 main에서 초기화하는 부분에서 한번만 해주고, 반복문 내에서 초기화해야할 때는 컬렉션의 clear()를 이용하도록 하자!

SWEA 풀이법

전략 수립

대응 방안 구상 - 필요한 이론

이 문제는 2차원 좌표 위에 주어진 원자들을 조건에 따라 움직여야 하므로, 2차원 배열을 이용하여 풀 수 있다.

2차원 배열을 이용하여 풀 때, 2차원 배열에 대한 이해가 필요하다!

  1. 2차원 배열의 기본 개념(배열 설계, 접근 인덱스 설계)

  2. 2차원 배열 탐색 방법

  3. 2차원 배열에서 경계 처리 방법

원자의 정보 저장

추후에 데이터 처리를 편리하게 하기 위해 좌표값에 1000을 더해 좌표값이 음이 아닌 정수가 되도록 조정해준다.🧐✅ => N*4 크기의 2차원 배열에 원자의 4가지 정보(x,y,방향,에너지) 를 저장

for(int i=0;i<N;i++){
    scanf("%d %d %d %d",&atom[i][0],&atom[i][1],&atom[i][2],&atom[i][3]);
    atom[i][0] += 1000;
    atom[i][1] += 1000;
}

문제 해결 과정

문제 해결을 위한 전처리 충돌을 확인하는 과정에서 주의해야할 점 모든 원자의 초기 좌표가 정수값을 갖더라도 충돌은 정수값의 좌표에서 일어나지 않을 수도 있다. //(0,0) => (0,1) 사이에 (0,0.5)에서 충돌이 난다면 이건 그냥 (0,1)에서 충돌처리해주면 되는 것 아닌가?

두 원자가 수평선 위에서 거리의 차이가 짝수인 경우는 정수값을 갖는 좌표에서 충돌하지만, 두 거리의 차이가 홀수인 경우, 정수값이 아닌 좌표에서 충돌한다.

그렇기 때문에 모든 원자들의 위치를 2배로 늘려서 원자들이 정수값을 갖는 좌표에서 충돌이 나도록 할 수 있다. 기존의 원자값들이 -1000<=x,y<=1000 값을 갖던 것에서 1000씩 더해 양수 값을 갖도록 하고ㅗ, 이를 2배씩 늘림으로써 x,y좌표는 0<=x,y<=4000 값을 갖게 한다.

원자 이동 시키기 원자마다 고유의 방향으로 한 칸씩 이동시킨 후 해당 위치에 원자가 2개 이상이면 이들은 서로 충돌을 한 것이므로, 충돌한 원자들을 제거하고, 보유한 에너지를 저장하는 것으로 문제를 해결할 수 있다. 먼저 원자들을 각자 고유한 방향대로 이동시킨다. 이 과정에서 기존의 좌표값(0<=x,y<=4,000)을 벗어난 원자들은 절대 충돌을 할 수 없으므로 이를 제거한다. 새롭게 이동한 위치에 visited[x][y] 값을 1 증가시켜 해당 위치에 원자가 하나가 추가되었음을 표시한다. 이 과정에서 현재 위치의 원자들의 갯수가 2개 이상이면 collided[x][y] 배열을 통해 충돌이 있음을 표시한다. 원자를 이동시키는 코드 :

원자 충돌 처리하기 모든 원자들을 이동시켰으면 원자들을 다시 순회하면서 원자가 현재 자리한 위치에 충돌이 있었는지 확인한다. 충돌이 있었으면 해당 원자를 제거하고, 원자가 분출하는 에너지를 추가 저장한다. 원자를 제거하는 과정은 현재 충돌 가능한 마지막 원자를 제거할 원자의 위치에 덮어씀으로써 제거한다. 그리고 충돌가능한 원자의 갯수를 하나 줄임으로써 마지막으로 옮겨진 원자는 무시할 수 있다. 원자를 제거하면서 남은 원자의 갯수를 확인하는 변수의 값도 하나씩 줄인다. 더 이상 충돌 가능한 원자가 남아있지 않을 때 해당 테스트 케이스 종료한다.

시간 복잡도 계산

Previous핀볼 게임Next무선 충전

Last updated