[C++] 백준 19236번 청소년 상어

19236번: 청소년 상어

삼성 SW 역량 테스트 기출 문제 수록 문제.

테스트 케이스가 잘 주어져 있어서 테스트 케이스만 잘 맞춘다면 대체로 맞는 것 같다.

구현 / 시뮬레이션 문제.

 

문제 조건

문제의 조건을 다음과 같이 정리할 수 있다.

• 4 * 4 공간이 존재하고, 1 * 1 크기인 한 칸마다 (x, y)에 물고기가 한 마리 존재한다.
• 각 물고기는 번호와 방향이 존재하고, 번호는 1 ~ 16 / 방향은 1부터 8까지이며 상하좌우 + 대각선이다.

 

문제는 상어와 물고기의 이동으로 이루어 지는데, 다음과 같은 순서로 이루어진다.

1. 청소년 상어가 (0, 0)에 있는 물고기를 먹고 해당 물고기의 방향을 갖는다.
2. 물고기들이 이동하는데, 번호가 작은 물고기부터 이동한다.
   1) 이 때, 경계선을 넘어가거나 상어가 존재하는 칸에는 이동할 수 없다.
   2) 이동하지 못한다면 반시계 방향으로 45도 회전해보고, 이동 못하면 이동하지 않는다.
   3) 다른 물고기가 있는 칸으로 이동은 서로의 위치를 변경한다.
3. 상어가 방향에 따라 이동한다.
   1) 상어는 여러 칸을 이동할 수 있는데, 이동하며 중간에서 만난 물고기는 먹지 않는다.
   2) 상어는 물고기가 있는 칸만 이동이 가능하다.
   3) 물고기를 먹으면, 상어의 방향은 해당 물고기의 방향이 된다.
   4) 이동할 수 없으면 집으로 돌아간다.
4. 3에서 상어가 이동했다면, 다시 2로 돌아간다.

후에 먹을 수 있는 물고기 번호 합의 최댓값을 출력하면 된다.

 

문제 코드

 

/*
* 백준 19236번 청소년 상어
* https://www.acmicpc.net/problem/19236
* - 구현 / 시뮬레이션
*/
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

struct Fish {
	bool isAlive = true;
	int x = 0;
	int y = 0;
	int direction = 0;
	int number = 0;
};

struct Shark {
	int x = 1;
	int y = 1;
	int direction = 0;
};

struct CurrentState {
	int score = 0;
	Shark shark;
	Fish fishArr[17][17];
	pair<int, int> fishPosition[17];
};

// 1부터 반시계방향
pair<int, int> directions[9] = {
	{0, 0},
	{-1, 0},
	{-1, -1},
	{0, -1},
	{1, -1},
	{1, 0},
	{1, 1},
	{0, 1},
	{-1, 1}
};

int result = 0;
queue<CurrentState> stateQueue;

void go() {
	while (!stateQueue.empty()) {
		CurrentState currentState = stateQueue.front();
		stateQueue.pop();

		result = max(result, currentState.score);

		//cout << currentState.shark.x << " , " << currentState.shark.y << "-" << currentState.score << "\n\n";

		//for (int x = 1; x <= 4; x++) {
		//	for (int y = 1; y <= 4; y++) {
		//		cout << "{" << currentState.fishArr[x][y].number << " , " << currentState.fishArr[x][y].direction << " , ";
		//		cout << currentState.fishArr[x][y].isAlive << "} ";
		//	}
		//	cout << "\n";
		//}
		//cout << "\n";

		//1. 물고기 이동
		for (int i = 1; i <= 16; i++) {
			int x = currentState.fishPosition[i].first;
			int y = currentState.fishPosition[i].second;

			//cout << i << " = " << x << " , " << y << "\n";
			//cout << "direction = " << currentState.fishArr[x][y].direction << "\n";

			if (!currentState.fishArr[x][y].isAlive) continue;

			int moveIdx = 9;
			while (moveIdx--) {
				int nxtX = x + directions[currentState.fishArr[x][y].direction].first;
				int nxtY = y + directions[currentState.fishArr[x][y].direction].second;

				if (nxtX < 1 || nxtX > 4 || nxtY < 1 || nxtY > 4 ||
					(nxtX == currentState.shark.x && nxtY == currentState.shark.y)) {
					currentState.fishArr[x][y].direction++;
					if (currentState.fishArr[x][y].direction > 8) currentState.fishArr[x][y].direction = 1;
					continue;
				}


				Fish tmpFish = currentState.fishArr[nxtX][nxtY];
				currentState.fishPosition[currentState.fishArr[x][y].number] = { nxtX, nxtY };
				currentState.fishPosition[currentState.fishArr[nxtX][nxtY].number] = { x, y };
				currentState.fishArr[nxtX][nxtY] = currentState.fishArr[x][y];
				currentState.fishArr[x][y] = tmpFish;

				break;
				
			}
		}


		// 2. 상어 이동
		int sharkNxtX = currentState.shark.x + directions[currentState.shark.direction].first;
		int sharkNxtY = currentState.shark.y + directions[currentState.shark.direction].second;

		while (sharkNxtX > 0 && sharkNxtX < 5 && sharkNxtY > 0 && sharkNxtY < 5) {
			if (currentState.fishArr[sharkNxtX][sharkNxtY].isAlive) {
				CurrentState nxtState = currentState;
				nxtState.fishArr[sharkNxtX][sharkNxtY].isAlive = false;
				nxtState.score += currentState.fishArr[sharkNxtX][sharkNxtY].number;
				nxtState.shark.direction = nxtState.fishArr[sharkNxtX][sharkNxtY].direction;
				nxtState.shark.x = sharkNxtX;
				nxtState.shark.y = sharkNxtY;

				stateQueue.push(nxtState);
			}
			sharkNxtX = sharkNxtX + directions[currentState.shark.direction].first;
			sharkNxtY = sharkNxtY + directions[currentState.shark.direction].second;
		}
	}
}

int main() {

	CurrentState firstState;
	
	int number, direction;
	for (int x = 1; x <= 4; x++) {
		for (int y = 1; y <= 4; y++) {
			cin >> number >> direction;
			firstState.fishArr[x][y].number = number;
			firstState.fishArr[x][y].direction = direction;
			firstState.fishPosition[number] = { x, y };
		}
	}

	firstState.fishArr[1][1].isAlive = false;
	firstState.score += firstState.fishArr[1][1].number;
	result += firstState.score;
	firstState.shark.direction = firstState.fishArr[1][1].direction;

	stateQueue.push(firstState);

	go();

	cout << result;

	return 0;
	
}

• 물고기 구조체
  1) 살아 있는 지 여부
  2) 좌표
  3) 방향
  4) 번호
  를 저장한다.
• 상어 구조체
  1) 좌표
  2) 방향
  을 저장한다.
• 현재 상태 구조체
  1) 현재까지 점수
  2) 상어 정보
  3) 물고기 배열 정보
  4) 1~16번까지 물고기들의 좌표
  를 저장한다.

현재 상태를 담은 큐를 이용해서 큐가 비지 않을 때까지 상어와 물고기를 이동시켜보고 점수의 최대값을 기록한다.

 

디버깅 오래 걸린 이유

1. 물고기 배열의 정보를 업데이트 할 때, 물고기 위치 배열을 업데이트를 안함.
   
   
2. 물고기를 이동시킬 때, 물고기 정보 업데이트의 순서를 잘못함.
   
   
3. 이동시킬 칸에 물고기가 죽어 있을 때와 구분함. 그러나 구분할 필요 없음.