21611번: 마법사 상어와 블리자드
마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그, 비바라기 마법을 할 수 있다. 오늘 새로 배운 마법은 블리자드이고, 크기가 N×N인 격자에서 연습하려고 한다. N은 항상 홀수이고, (
www.acmicpc.net
2021 삼성 인턴 기출문제였다고 합니다.
어렵다는 말이 많아서 한번 풀어봤더니 64%에서 런타임 에러가 났습니다;;
원인을 분석해본 결과
3 1
1 1 1
1 0 1
1 1 1
3 1
과 같은 테케를 넣었을 경우 모든 구슬이 사라지는 경우가 발생하는데
큐를 사용하여 구현했던 저는 여기서 터졌습니다.
아무것도 없는 큐에서 값을 pop하려 하니 런타임 에러가 발생한 것이었고
이를 고쳐주니 문제를 맞출 수 있었습니다.
문제풀이 :
문제에서 (n/2, n/2) 으로부터 회전 회오리를 돌면서 좌표를 찍어나가야합니다.
회전 회오리를 돌때 규칙을 보면 왼쪽 1칸, 아래 1칸, 오른쪽 2칸, 위쪽 2칸 ... 이런식으로
1 <= n < 7까지 각 방향을 2번씩 순회하는데 맨 마지막에만 3번을 순회한다.
이거를 반복분을 통해 작성하였고 이 틀을 통해 나머지 함수들을 작성하였다.
각 함수를 설명하자면
marble_move() : 빈칸을 매꿔주는 함수이다.
boom() : 구슬을 터트리는 함수이고 더이상 터트릴 구슬이 없으면 return false 이다.
make_new() : 남아있는 구슬을 통해 새로운 구슬을 만들어주는 함수이다.
skill() : 상어자식이 스킬을 쓰는 함수이다.
저는 queue를 이용해서 구현을 했습니다.
위에서도 써놨듯이 queue를 이용할 경우 비어있을 때 빼내는 경우가 있는지 없는지 판단을 잘해야합니다.
회전 회오리 하는 좌표를 pair<int,int> w[250] 라는 배열에 담아서 하면 더 구현하기 쉽지 않을까
생각이 드는데 나중에 다시 한번 풀어봐야 겠습니다.
코드 :
'Algorithm' 카테고리의 다른 글
| 백준 - 8111번(0과 1) / C++ (4) | 2021.04.05 |
|---|---|
| 백준 - 1285번(동전 뒤집기) / C++ (0) | 2021.03.26 |
| 프로그래머스 - 카드 짝 맞추기 / C++ (2) | 2021.03.24 |
| 백준 - 14442번(벽 부수고 이동하기 2) / C++ (4) | 2021.03.16 |
| 백준 - 14939번(불 끄기) / C++ (0) | 2021.03.12 |