백준 21611. 마법사 상어와 블리자드

https://www.acmicpc.net/problem/21611

21611번: 마법사 상어와 블리자드

 

상어 시리즈 문제.

구현할게 상당히 많은, 거의 막힘 없이 푼다고 해도 시간이 꽤나 걸릴것 같은 문제다.

제출해서 틀리면 진짜 맨탈 터질것 같은 문제인데 다행히 한번에 맞았다.

이런 코드가 길어지는 단순 구현 문제는 진짜 한번 할때 꼼꼼히 봐야지 제출 했는데 틀리면 틀린곳 찾기 정말 힘들다.

 

 

 

(1) 보드 달팽이 모양으로 순회 

우선 이 문제에서 구현해야할 첫번째이자 가장 중요한 로직은 위 보드를 순서대로 순회하는 로직이다.

그런데 문제를 보면 중간중간 빈 공간이 생기게 되고 작은 번호쪽으로 구슬이 움직이게 된다.

그 말은 순회의 순서가 큰번호->작은번호 여야지 반대로 하게 되면 구슬을 땡겨줄때 데이터 손실이 발생한다.

 

예를들어 3번칸이 비어서 4번칸에 있는 구슬이 3번으로 땡겨질때를 생각해보자.

3번칸에서 다음칸인 4번칸을 보고, 4번칸에 있는 구슬을 3번으로 땡겨와야한다.

반대로 4번칸에서 3번칸으로 구슬을 밀어버리면 3번칸에 있는 데이터가 손실된다.

 

그런데 이런 달팽이 모양 순회 구현은 밖에서부터 안으로 순회가 쉽다. 

1) 처음시작에서 오른쪽으로 갈수 있을때까지 간다.

2) 아래로 갈수 있을때까지 간다.

3) 왼쪽으로 갈수 있을때까지 간다.

4) 위로갈수 있을때까지 간다.

 

여기서 갈수 있을때라는건 범위 내 아직 방문하지 않은 곳이다.

 

그런데 우리는 안에서부터 밖으로 순회해야 하는데 방법이 있다.

위 로직을 재귀적으로 수행해서 끝까지 도달시 다시 return 하도록 하면, 되돌아 오면서 반대로 방문할수 있다.

코드에서 dfs() 함수가 이를 수행한다.

 

반대로 돌아오면서 좌표를 벡터에 저장해놓으면 이제부터는 해당 벡터를 순회하기만 하면 우리는 보드를 우리가 원하는 순서대로 방문할수 있다.

 

 

(2) 빈 곳으로 구슬 이동 

다음으로 중요한 로직은 비어 있는 공간을 구슬로 채우는 로직이다.

우리는 이미 좌표 순서의 벡터를 구해놨기 때문에 순서대로 방문하면서 땡겨주면 된다.

 

그런데 주의할 점이 있다.

땡겨주는 로직을 한번만 수행하면 안되고, 비어있는 칸 수 만큼 수행해줘야 한다.

 

마법사 상어가 거리 s 만큼 블리자드를 쏘았으면 s 만큼 빈 공간이 생기기 때문에 s 번 반복하면 된다.

 

 

(3) 구슬 폭발, 구슬 변화

이 두 로직은 거의 동일하다.

폭발은 보드를 순서대로 방문하면서 연속된곳을 찾고 0으로 지워주고 구슬 이동 로직을 폭발한 구슬만큼 반복해준다.

변화도 마찬가지로 순서대로 방문하면서 구슬번호와 갯수를 기록하고, 순서대로 보드에 채워준다.