[C++] 백준 16236번 아기 상어

구현 / 시뮬레이션 + BFS(너비 우선 탐색) 문제.

테스트 케이스가 상당히 많고 잘 돼 있어서 디버깅을 하다보면 맞출 수 있다.

처음에 4번째 테스트 케이스가 자꾸 다른 값(60이 아니라 56)이 나와서 뭐가 잘못됐는지 모르겠어서

백준 게시판에 봤더니 고려해 주지 못한 부분이 있었다.

아마 테스트 케이스들만 올바른 방향으로 통과한다면 맞출 수 있을 것이다.

 

문제풀이

아기상어는 다음과 같은 조건을 갖는다.

• 이동은 상, 하, 좌, 우 방향으로 가능하다.
• 이동하는데는 1초의 시간이 소요가 된다.
• 처음 아기상어의 크기는 2이고 자신의 크기만큼 물고기를 먹으면 크기가 증가한다.
• 자신의 크기보다 큰 물고기가 있는 곳은 지나가지 못하고, 같은 물고기가 있는 곳은 지나가기는 가능하며, 더 작은 물고기가 있는 곳은 해당 물고기를 잡아먹고 지나간다.
• 먹을 수 있는 물고기가 있다면 해당 물고기를 먹으러 간다.

마지막 조건을 더 세세하게 살펴보자.

• 먹을수 있는 물고기가 여러개라면 위에있는 것부터, 많다면 왼쪽에 있는 것부터 먹는다.

		1. 물고기
	2. 물고기		3. 물고기
4. 물고기		현재 위치		5. 물고기
	6. 물고기		7. 물고기
		8. 물고기

만일 위와 같이 아기상어의 주변에 거리가 2인 물고기들이 여러개가 있다고 가정해보자.

그러면 우선순위를 물고기 왼쪽 숫자처럼 나눌 수 있을 것이다.

이게 중요한 게 만일 5번 우선순위 물고기와 6번 우선순위 물고기가 있을 때,

BFS를 상, 좌, 우, 하의 순서로 돌리게 되므로 5번 물고기보다 6번 물고기에 먼저 접근하게 된다.

 

나같은 경우는 이런 우선순위를 나눠주지 않아서 테스트 케이스 4번이 제대로 나오지 않았다.

 

해당 조건들만 고려한다면 맞출 수 있다.

 

사용한 STL과 변수

• widthHeight : 공간의 크기 N
• sea 배열 : 각 칸에서 물고기의 정보를 저장할 배열
• visit : BFS를 할 때, 해당 정점을 방문했는지 여부를 저장할 배열
• findFood : BFS를 돌렸을 때, 먹을 수 있는 물고기를 찾았는지 저장할 변수
• curSize : 현재 아기상어의 크기
• curEat : 현재 아기상어가 먹은 물고기의 수
• needEat : 아기상어가 해당 크기에서 크기가 +1 되기위해 아기상어가 먹어야 할 물고기의 수, 물고기들의 최대 크기가 6이므로 7부터는 고려하지 않아도 된다.
• curY, curX : 현재 아기상어의 좌표
• foodInfo : 아기상어가 BFS를 돌면서 찾은 먹을 수 있는 물고기의 정보, 이중 pair형태인데 첫번째는 거리, 두번째 pair의 첫번째는 Y좌표, 두번째는 X좌표를 담는다.
• timeSec : 시간이 얼마나 지났는지 저장하는 배열. 출력값이다.
• direction 배열 : 순서대로 상좌우하로 이동하게 만들어주는 배열.

그리고 memset 메서드를 사용하기 위해 cstring STL과 BFS를 하기위해 queue STL을 사용했다.

 

메인함수 - 1

시작에 크기를 입력받고 공간의 각 칸의 정보를 입력받는다.

9라는 것은 아기상어의 위치이므로 curY, curX 좌표에 저장해둔다. 그리고 해당 칸을 0으로 만든다.

 

메인함수 - 2

반복문의 조건이 먹이를 찾았는가?인데

처음에 무조건 실행할 수 있도록 do While문을 사용했다.

지금 생각해보니 처음에 그냥 findFood를 true로 초기화한 후 했어도 상관없었을 것 같다.

 

반복문에 들어가면 처음에 findFood를 false로 만들어줘서 먹이를 찾지 않은 상태로 만든다.

그리고 memset메서드로 방문했던 기록들을 모두 없애준다. visit 배열을 false로 초기화한다.

 

그리고 먹이의 정보를 담는 foodInfo의 정보를 다음과 같이 초기화한다.

• 거리는 1e10(1000000000)으로 만든다. 거리가 가까운 것을 먹어야 한다. 거리는 항상 1e10보다 작으므로 처음 만난 먹을 수 있는 물고기의 정보로 무조건 갱신이 된다.
• Y좌표도 1e10인데, 위에있는 것을 먼저 먹어야한다. 즉, Y좌표가 작은 물고기들을 먼저 먹어야 한다. 그러므로 Y좌표를 1e10으로 초기화하면 처음 먹을 수 있는 물고기 정보로 무조건 갱신이 된다.
• X좌표도 1e10이다. 좌측에 있는 것 먼저 먹어야 하므로 X좌표가 작은 물고기들을 먼저 먹어야 한다. X좌표도 이와같이 초기화 하면 처음 만난 먹을 수 있는 물고기는 무조건 정보가 갱신이 된다.

그리고 현재 좌표에서 BFS를 시작해서 먹이를 찾는다.

 

만일 먹이를 찾았다면

1. 지난 시간을 거리만큼 추가시킨다.
2. 해당 칸을 0으로 만든다.
3. 먹은 물고기 수를 1 증가시킨다. 이 때, 자신의 크기만큼 물고기를 먹었다면 아기상어의 크기를 증가시킨다.
4. 현재 좌표를 먹은 물고기의 좌표로 만들어 준다.

 

먹이를 찾지 못했다면 반복문을 빠져나와서 지난 시간을 출력해준다.

 

BFS - 1

BFS의 시작에 큐를 만들어 준다. 큐의 자료형은 먹이의 정보를 담는 이중 pair 형태와 동일하다.

그리고 시작 정점에 방문했다고 기록한 후 반복문에 진입한다.

현재 탐색하는 칸의 거리, Y좌표 X좌표를 불러오고 큐에서 pop해준다.

그리고 현재 저장중인 먹이의 거리, Y좌표, X좌표를 불러온다.

 

만일 저장중인 먹이의 거리보다 현재 탐색하는 칸의 거리가 더 멀다면 BFS를 종료한다.

너비 우선 탐색이므로 저장중인 먹이의 거리보다 먼 곳은 고려해줄 필요가 없다.

저장중인 먹이의 거리보다 작거나 같은 곳들은 이미 모두 탐색이 되어있다.

 

BFS - 2

그리고 해당 칸이 0이 아니면서 현재 아기상어의 size보다 작다면 다음과 같은 조건들을 고려해서 update 해준다.

• 현재 Y좌표가 찾아놨던 먹을 수 있는 물고기의 Y좌표보다 크다면?(아래에 있다면) 고려하지 않는다.
• 현재 Y좌표가 찾아놨던 먹을 수 있는 물고기의 Y좌표와 같지만 X좌표가 더 크다면?(우측에 있다면) 고려하지 않는다.
• 그 이외에 Y좌표가 더 작고(위에있고) Y좌표가 같지만 X좌표가 작다면 먹을 수 있는 물고기의 정보를 새로 갱신해준다.
• 그리고 먹이를 찾아놨다고 findFood bool변수에 저장해준다.

그리고 만일 현재 칸이 아기상어의 현재 사이즈보다 크다면 고려하지 않고 넘어간다.

 

BFS - 3

 

그리고 현재 탐색중인 칸에서 상, 좌, 우, 하의 순서대로 BFS 큐에 삽입한다.

만일 다음에 탐색할 좌표가 공간을 벗어나거나, 이미 방문한 곳이라면 고려하지 않는다.

그리고 BFS 큐에 해당 좌표의 정보들을 넣고 방문했다고 기록을 남긴다.

 

생각보다 어렵다는 평가가 많았는데, 한 번에 맞췄다.

아마 운이 좋았던 것 같고 4번 테스트 케이스가 잘 돼 있어서 좋았다.

물론 미쳐 고려하지 못한 부분은 게시판의 도움을 받기도 했다. 이 부분이 제일 중요한 부분이었다.

 

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

코드는 위에서 확인이 가능하다.