[C++] 마법사 상어와 비바라기

구현 / 시뮬레이션 문제.

삼성 SW 역량 테스트 기출 문제였다.

삼성은 구현하는 문제를 참 좋아하는 것 같다.

천천히 정리하고 생각한 로직대로 풀면 되는 문제다.

 

문제풀이

문제의 주요 내용들을 정리해보자면 다음과 같다.

• 구름의 이동은 1행과 N행, 1열과 N열이 연결되어 있다. -> N + 1 -> 1, 0 -> N이 되면 된다.
• 최초 비바라기 시전 시 (N - 1, 1), (N - 1, 2), (N, 1), (N, 2)에 구름이 생긴다.
• 비바라기 시전 후에는 아래 로직들이 M번 반복된다.

1. 모든 구름을 방향 D로 S번 이동한다.
2. 모든 구름의 이동을 마치고 나면, 물의 양을 1 증가한다. 그리고 구름이 사라진다.
3. 구름이 있던 곳에 물 복사 버그를 한다. 대각선 방향에 물이 있는 바구니의 수만큼 해당 지점에 물을 증가시키는데, 이 때는 1행과 N행, 1열과 N열이 연결되어있지 않다.
4. 물의 양이 2 이상인 모든 곳에 구름을 생성하고 물의 양을 2 감소시킨다. 이 때 (2)에서 구름이 사라진 곳은 제외한다.

추가로 고려해야할 사항들은

• (2)에서 구름이 사라질 때, 구름의 좌표들은 기억해뒀다가 물복사 버그를 해야한다. 따라서 물복사 버그 이후에 구름의 좌표들을 지우는 방식으로 구현해도 된다.
• 방향의 시작 idx는 0이 아니라 1부터이다. 따라서 (3)에서 대각선의 방향은 2, 4, 6, 8이다.

 

위의 내용을 토대로 구현하면 된다.

사용한 STL과 변수

• widthHeight : 격자의 크기 N
• testCastCnt : 구름을 이동시키는 횟수.
• board 배열 : 현재 격자에서 물의 양을 저장하는 2차원 배열
• check 배열 : 3차원 배열인데, 해당 단계에서 해당 좌표가 구름으로 만들어졌었는지 기록하기 위한 배열이다. 이를 통해 마지막에 물의 양이 2이상인 곳에 구름을 생성할 때, 확인할 수 있다.
• curStage, curDirection, curMovement : 순서대로 - 현재 몇번째 이동인지, 입력받은 방향(d), 입력받은 움직이는 수(s)
• ans : 출력하는 결과값
• cloudPoint 벡터: 구름이 있는 좌표를 기록하는 벡터. 일일이 찾기보다 저장해두는 것이 더 빠르게 찾을 수 있다.
• direction 배열 : 1 ~ 8 idx가 순차적으로 문제의 조건에 맞는 방향을 제시해준다. 좌표에 더해주기만 하면 됨.

메인함수 - 1

처음에 격자의 크기 N, 그리고 이동 횟수 M을 입력받는다.

그리고 나서 격자의 각 칸에 현재 물의 양을 입력받는다.

 

최초 비바라기는 4곳에 생기는데 해당 좌표들을 구름의 좌표를 저장하는 벡터 cloudPoint에 저장해둔다.

 

메인함수 - 2

그런 후에, 반복문을 이동횟수만큼 반복한다. 

반복문에서는 처음에 이동하는 방향 d와 이동횟수 s를 입력받는다.

그리고 저장중인 구름 좌표들의 좌표를 이동시킨다.

 

이동이 완료됐다면 해당 좌표의 물의 양을 증가시킨다.

메인함수 - 3

물복사버그 메서드

그러고난 후에, 물복사버그를 진행한다. 각 좌표에서 대각선 방향을 고려해주면 된다.

구름의 이동과는 다르게 1행과 N행, 1열과 N열이 연결돼 있지 않다는 것이 주의할 점이다.

 

물복사버그를 진행한 후에는 구름의 좌표들을 지워줌으로써, 구름을 지워준다.

어차피 나는 현재 단계에서 생긴 구름들은 check 배열로 저장해두었기 때문에 상관없다.

 

그리고 물의 양이 2이상이고, 현재 단계에서 구름이 생성되지 않은 곳에 구름을 생성하고 물의 양을 2를 빼준다.

 

이동을 완료했다면, 모든 격자칸의 값을 다 더해 총 물의 양을 구해서 출력하면 된다.

 

 

GitHub - kimyunseok/study-record: my study-record

코드 전문은 위에서 확인이 가능하다.