[19236번 청소년 상어] - C++

[19236번 청소년 상어]
https://www.acmicpc.net/problem/19236

[19237번 어른 상어]
https://www.acmicpc.net/problem/19237
https://velog.io/@statco19/boj-19237

[16236번 아기 상어]
https://www.acmicpc.net/problem/16236
https://velog.io/@statco19/boj-16236

아기 - 청소년 - 어른 상어로 이어지는 시리즈 중 중간에 있는 문제이다. 체감 난이도는 청소년 상어가 가장 까다로웠다.

일단 상어가 먹을 수 있는 물고기 크기의 최대값을 구해야 하기 때문에 가능한 모든 경우를 백트래킹으로 살펴봐야 한다. 그 점에서 DFS 알고리즘을 사용해야 함을 알 수 있었다. 그리고 2차원 배열의 크기가 4*4인 점을 보면 DFS를 사용해도 시간초과가 나지 않을 만큼 연산이 많지 않을 것을 알 수 있었다.

풀이

물고기의 크기를 2차원 배열 size_에 넣어주었고, 물고기의 방향을 2차원 배열 dir에 넣어주었다.

void dfs(int r, int c, int score) {
	// 상어를 (0,0)에 넣어주고 (0,0)에 있던 물고기 먹고 score에 크기 더해줌
    
    // 물고기 이동
    
    // 상어가 바라보는 방향에 물고기가 더 이상 없으면,
    // 갈 곳이 없으므로 종료
    if(sharkGoesHome(r,c,d)) {
		ans = max(ans, score);
		return;
	}
    
    // 상어가 바라보는 방향에 물고기가 있다면, 잡아먹으러 이동
    	// 잡아먹으러 가는 물고기의 위치를 (R,C)라고 하면
        dfs(R,C,score);
        
    return;
}

핵심이 되는 수도코드 부분을 이렇게 짜고 중간중간에 추가적인 메서드를 구현했다. 주의할 점은 상어가 물고기가 없는 칸을 발견하자마자 집으로 가는 것이 아닌 자기가 바라보는 방향에서 끝까지 한 마리도 물고기가 존재하지 않아야 집으로 돌아가도록 구현해야 한다.

C++ 코드

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <utility>  // pair
#include <tuple>
#include <stack>
// #include <map>
#include <unordered_map>
#define ll long long
#define INF 1e9
using namespace std;

int ans = 0;
int size_[4][4];
int dir[4][4];
int dr[] = {0,-1,-1,0,1,1,1,0,-1};
int dc[] = {0,0,-1,-1,-1,0,1,1,1};
int sharkR;
int sharkC;

int sharkGoesHome(int r, int c, int d) {
	int nr,nc;
	nr = r+dr[d];
	nc = c+dc[d];

	while(0<=nr&&nr<4 && 0<=nc&&nc<4) {
		if(size_[nr][nc] > 0) {  // fish exist
			return 0;
		}
		nr += dr[d];
		nc += dc[d];
	}
	return 1;
}

void move(int r, int c, int d) {
	int nd,nr,nc;
	for(int i=0;i<8;++i) {
		nd = (d-1+i)%8 + 1;
		nr = r+dr[nd];
		nc = c+dc[nd];

		if(0<=nr&&nr<4 && 0<=nc&&nc<4) {
			if(nr==sharkR && nc==sharkC) {  // shark
				continue;
			} else {
				if(size_[nr][nc] > 0) {  // fish
					dir[r][c] = nd;

					int tempSize = size_[nr][nc];
					int tempDir = dir[nr][nc];

					size_[nr][nc] = size_[r][c];
					dir[nr][nc] = dir[r][c];

					size_[r][c] = tempSize;
					dir[r][c] = tempDir;

					return;
				} else if(size_[nr][nc]==0) {  // empty
					dir[r][c] = nd;

					size_[nr][nc] = size_[r][c];
					dir[nr][nc] = dir[r][c];

					size_[r][c] = 0;
					dir[r][c] = 0;

					return;
				}
			}
		}
	}
	return;
}

void moveFish() {
	int num = 1;
	while(num<=16) {
		int found = 0;
		for(int i=0;i<4;++i) {
			for(int j=0;j<4;++j) {
				if(size_[i][j] == num) {
					int d = dir[i][j];
					move(i,j,d);
					found = 1;
					break;
				}
			}
			if(found) break;
		}
		num++;
	}
	return;
}

void dfs(int r, int c,int score) {
	sharkR = r; sharkC = c;
	score += size_[r][c];
	size_[r][c] = 0;
	int d = dir[r][c];
	dir[r][c] = 0;

	moveFish();

	if(sharkGoesHome(r,c,d)) {
		ans = max(ans, score);
		return;
	}

	int size__cpy[4][4];
	int dir_cpy[4][4];
	copy(&size_[0][0], &size_[0][0]+16, &size__cpy[0][0]);
	copy(&dir[0][0], &dir[0][0]+16, &dir_cpy[0][0]);

	int nr,nc;
	nr = r+dr[d];
	nc = c+dc[d];
	while(0<=nr&&nr<4 && 0<=nc&&nc<4) {
		if(size_[nr][nc] > 0) {  // fish exist
			size_[r][c] = 0;  // shark leaves
			dfs(nr,nc,score);

			sharkR = r; sharkC = c; 
			copy(&size__cpy[0][0], &size__cpy[0][0]+16, &size_[0][0]);
			copy(&dir_cpy[0][0], &dir_cpy[0][0]+16, &dir[0][0]);
		}
		nr += dr[d];
		nc += dc[d];
	}
	return;
}

int main(void) {
	// ios_base :: sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	for(int i=0;i<4;++i) {
		for(int j=0;j<4;++j) {
			scanf("%d%d", &size_[i][j], &dir[i][j]);
		}
	}
	dfs(0,0,0);	
	printf("%d\n", ans);
	
	return 0;
}

실행 결과