[BOJ] 백준 23290 마법사 상어와 복제

Approach

출처: https://www.acmicpc.net/problem/23290

 

실제 시험장에서 문제 설명과 Test Case는 알 수 없지만,,,

문제 조건이 갈수록 이해하기 어려워지는 경향이 있는 것 같네요 😒

 

이번 문제는 시뮬레이션 구현 문제로

주어진 Test Case를 하나하나 따라가다 보면 구현할 수 있는데

문제 조건과 함께 DFS와 BFS 구현을 해야 했던 것 같습니다.

void process()
{
        while (S--)
        {
               copyMagic(SAVE);
               moveFish();
               removeSmell();
               moveShark();
               copyMagic(LOAD);
        }
}

① 물고기 저장 (복제 마법)

② 물고기 이동

③ (기존) 물고기 냄새 처리

④ 상어 이동

⑤ 저장한 물고기 반영

복제 마법

inline void copyMagic(int mode)
{
        switch (mode)
        {
        case SAVE: // 물고기 저장
               _memcpy(copyMap, map);
               break;

        case LOAD: // 저장해둔 물고기를 좌표에 push
               for (int i = 1; i <= N; ++i)
               {
                       for (int j = 1; j <= N; ++j)
                       {
                              for (int k = 0; k < copyMap[i][j].size(); k++)
                              {
                                      
                                      map[i][j].push_back(copyMap[i][j][k]);
                              }
                       }
               }
               break;
        }
}

물고기를 저장하는 것과 반영하는 것을 하나의 함수에서 처리했습니다.

실제 문제 풀 때는 두 개의 함수로 처리하는 것이 좋겠죠..?

물고기가 이동하기전에 copyMap[][]에 복사해두고

Process Cycle 한 번 끝날 때 저장해둔 물고기를 map[][]에 반영

 

* map[][]은 물고기 객체를 저장할 수 있도록 vector 활용

vector<Node> map[MAX_N][MAX_N];

 

물고기 이동

Node move(Node cur)
{
        int nextX = cur.x;
        int nextY = cur.y;
        
        for (int d = 0; d < 8; d++)
        {
               nextX = cur.x + fdx[cur.dir];
               nextY = cur.y + fdy[cur.dir];
               if (nextX >= 1 && nextX <= N && nextY >= 1 && nextY <= N)
               {
                       if (!(nextX == shark.x && nextY == shark.y)
                              && fishSmellMap[nextX][nextY] == 0)
                       {
                              // 물고기가 이동가능한 경우
                              return { nextX, nextY, cur.dir };
                       }
               }
               // 방향 전환
               cur.dir = rotateDir(cur.dir);
        }
        // 이동하지 못하는 경우
        return cur;
}

void moveFish()
{
        vector<Node> TMap[MAX_N][MAX_N];
        for (int i = 1; i <= N; i++)
        {
               for (int j = 1; j <= N; j++)
               {
                       for (int k = 0; k < map[i][j].size(); k++)
                       {
                              Node f = move(map[i][j][k]);
                              TMap[f.x][f.y].push_back({ f.x, f.y, f.dir });
                       }
               }
        }
        _memcpy(map, TMap);
}

map[][]에 있는 물고기들을 전체적으로 움직여 줍니다.

움직인 물고기를 다시 움직이지 않도록

초기 map[][]과 동일한 TMap[][] 만들어서

그 곳에 한마리씩 옮겨준 후 모두 끝나고 다시 map[][]에 옮겨주었습니다.

 

물고기가 이동할 때는 8개 방향을 살피는데

아래 조건들을 확인해야 합니다.

① 범위를 벗어나는 방향인지

② 상어가 있는 곳인지

③ 물고기 냄새가 남아 있는 곳인지

 

* 물고기 방향은 반시계 45도 방향 회전으로 아래와 같이 구현

int rotateDir(int d) { return (d - 1) == 0 ? 8 : (d -1); }

 

상어 이동

int huntFish()
{
        Node cur = { shark.x, shark.y };
        int ret = 0;
        bool visit[MAX_N][MAX_N] = { false, };
        for (int i = 0; i < 3; i++)
        {
               int dir = trr[i];
               int nextX = cur.x + sdx[dir];
               int nextY = cur.y + sdy[dir];
               // 경로를 벗어나는 경우
               if (nextX < 1 || nextX > N || nextY < 1 || nextY > N)
                       return -1;
               // 재방문 하지 않은 곳을 물고기 개수 더해주기
               if (!visit[nextX][nextY])
               {
                       visit[nextX][nextY] = true;
                       ret += map[nextX][nextY].size();
               }
               cur = { nextX, nextY };
        }
        return ret;
}

void DFS(int idx)
{
        if (idx == 3)
        {
               int val = huntFish();
               if (maxValue < val)
               {
                       // 경로 저장
                       for (int i = 0; i < 3; i++)
                       {
                              arr[i] = trr[i];
                       }
                       maxValue = val;
               }
               return;
        }
        for (int i = 1; i <= 4; ++i)
        {
               trr[idx] = i;
               DFS(idx + 1);
        }
}

void moveShark()
{
        maxValue = -1;
        DFS(0);
        for (int i = 0; i < 3; i++)
        {
               int nextX = shark.x + sdx[arr[i]];
               int nextY = shark.y + sdy[arr[i]];
               // 물고기가 존재한다면
               if (map[nextX][nextY].size() != 0)
               {
                       fishSmellMap[nextX][nextY] = 2;
                       map[nextX][nextY].clear();
               }
               shark = { nextX, nextY };
        }
}

 

상어 이동방향은 물고기를 가장 많이 먹을 수 있는 경로로 하되

동일한 경우 「사전순 우선순위」를 가집니다.

[상, 상, 상] → [상, 상, 좌] → … → [우, 우, 하] → [우, 우, 우]

 

이는 [1, 1, 1] → [1, 1, 2] → … → [4, 4, 3] → [4, 4, 4] 인데,

중복 순열/조합을 통해서 구현할 수 있다.

▶ 순열과 조합

순열과 조합 (백준 N과 M 시리즈)

문제에서 제시한 순서로 방향을 임시로 정해서

해당 [방향 구성]으로 물고기를 많이 먹는대로 방향을 갱신해준다.

 

익숙하지 않다면 실제 시험장에서는 DFS를 사용하지 않고 

64 가지 경우를 하드 코딩(LUT)하는 것도 해결책이 될 수 있습니다.

▶ 시간 성능 향상을 위한 코드 최적화 (C/C++)

[알고리즘] 시간 성능 향상을 위한 코드 최적화 (C/C++)

방향이 정해진 다음에는 이동하면서 물고기를 먹고

물고기 냄새를 남깁니다.

 

물고기 냄새 처리

void removeSmell()
{
        for (int i = 1; i <= N; i++)
        {
               for (int j = 1; j <= N; j++)
               {
                       if (fishSmellMap[i][j] > 0)
                              fishSmellMap[i][j]--;
               }
        }
}

물고기 냄새는 전체 map[][]에서 남아있는 냄새 감소

* 「물고기 냄새」가 있는 곳으로 이동은 불가하지만

    복제 마법으로 그 곳에 생성될 수는 있다 

---

#include <iostream>
#include <vector>

using namespace std;

struct Node
{
	int x, y, dir;
} shark;

enum Magic
{
	SAVE,
	LOAD
};

inline int rotateDir(int d) { return (d - 1) == 0 ? 8 : (d - 1); }
const int MAX_N = 5;
const int N = 4;
const int sdx[] = { 0, -1, 0, 1, 0 };
const int sdy[] = { 0, 0, -1, 0, 1 };
const int fdx[] = { 0, 0, -1, -1, -1, 0, 1, 1, 1 };
const int fdy[] = { 0, -1, -1, 0, 1, 1, 1, 0, -1 };

int M, S, maxValue, ans;
int arr[3], trr[3];
int fishSmellMap[MAX_N][MAX_N];
vector<Node> map[MAX_N][MAX_N], copyMap[MAX_N][MAX_N];

void input()
{
	scanf("%d %d", &M, &S);

	int x, y, d;
	for (int i = 0; i < M; i++)
	{
		scanf("%d %d %d", &x, &y, &d);
		Node f = { x, y, d };
		map[x][y].push_back(f);
	}

	scanf("%d %d", &shark.x, &shark.y);
}

inline void _memcpy(vector<Node> to[][MAX_N], vector<Node> from[][MAX_N])
{
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			to[i][j] = from[i][j];
		}
	}
}

inline void copyMagic(int mode)
{
	switch (mode)
	{
	case SAVE: // 물고기 저장
		_memcpy(copyMap, map);
		break;

	case LOAD: // 저장해둔 물고기를 좌표에 push
		for (int i = 1; i <= N; ++i)
		{
			for (int j = 1; j <= N; ++j)
			{
				for (int k = 0; k < copyMap[i][j].size(); k++)
				{

					map[i][j].push_back(copyMap[i][j][k]);
				}
			}
		}
		break;
	}
}

Node move(Node cur)
{
	int nextX = cur.x;
	int nextY = cur.y;

	for (int d = 0; d < 8; d++)
	{
		nextX = cur.x + fdx[cur.dir];
		nextY = cur.y + fdy[cur.dir];

		if (nextX >= 1 && nextX <= N && nextY >= 1 && nextY <= N)
		{
			if (!(nextX == shark.x && nextY == shark.y)
				&& fishSmellMap[nextX][nextY] == 0)
			{
				// 물고기가 이동가능한 경우
				return { nextX, nextY, cur.dir };
			}
		}

		// 방향 전환
		cur.dir = rotateDir(cur.dir);
	}

	// 이동하지 못하는 경우
	return cur;
}

void moveFish()
{
	vector<Node> TMap[MAX_N][MAX_N];

	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			for (int k = 0; k < map[i][j].size(); k++)
			{
				Node f = move(map[i][j][k]);
				TMap[f.x][f.y].push_back({ f.x, f.y, f.dir });
			}
		}
	}

	_memcpy(map, TMap);
}

int huntFish()
{
	Node cur = { shark.x, shark.y };
	int ret = 0;
	bool visit[MAX_N][MAX_N] = { false, };

	for (int i = 0; i < 3; i++)
	{
		int dir = trr[i];
		int nextX = cur.x + sdx[dir];
		int nextY = cur.y + sdy[dir];

		// 경로를 벗어나는 경우
		if (nextX < 1 || nextX > N || nextY < 1 || nextY > N)
			return -1;

		// 재방문 하지 않은 곳을 물고기 개수 더해주기
		if (!visit[nextX][nextY])
		{
			visit[nextX][nextY] = true;
			ret += map[nextX][nextY].size();
		}
		cur = { nextX, nextY };

	}
	return ret;
}

void DFS(int idx)
{
	if (idx == 3)
	{
		int val = huntFish();
		if (maxValue < val)
		{
			// 경로 저장
			for (int i = 0; i < 3; i++)
			{
				arr[i] = trr[i];
			}
			maxValue = val;
		}
		return;
	}

	for (int i = 1; i <= 4; ++i)
	{
		trr[idx] = i;
		DFS(idx + 1);
	}
}

void moveShark()
{
	maxValue = -1;
	DFS(0);

	for (int i = 0; i < 3; i++)
	{
		int nextX = shark.x + sdx[arr[i]];
		int nextY = shark.y + sdy[arr[i]];

		// 물고기가 존재한다면
		if (map[nextX][nextY].size() != 0)
		{
			fishSmellMap[nextX][nextY] = 2;
			map[nextX][nextY].clear();
		}

		shark = { nextX, nextY };
	}
}

void removeSmell()
{
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			if (fishSmellMap[i][j] > 0)
				fishSmellMap[i][j]--;
		}
	}
}

void process()
{
	while (S--)
	{
		copyMagic(SAVE);
		moveFish();
		removeSmell();
		moveShark();
		copyMagic(LOAD);
	}
}

void output()
{
	// 남아 있는 물고기
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			ans += map[i][j].size();
		}
	}
	printf("%d\n", ans);
}

int main()
{
	// freopen("Input.txt", "r", stdin);
	input();
	process();
	output();
}

 

📌 함께 보면 좋은 포스팅

• N과 M (3)

• 시간 성능 향상을 위한 코드 최적화 (C/C++)

• 순열과 조합

• 삼성 SW 기출 모음

• 삼성 SW 코딩 테스트 준비(A형)