[Algorithm][C++] BOJ 17143 낚시왕

url: https://www.acmicpc.net/problem/17143

17143번: 낚시왕

 

풀이 핵심

1. 상어가 벽을 만났을 때 방향 전환을 쉽게 하기 위해 dr, dc 배열과 GetReverseDir 함수를 이용한다.

const int dr[] = { 0,-1,1,0,0 };
const int dc[] = { 0,0,0,1,-1 };

// 1-->Up, 2--> Down, 3-->Right, 4-->Left
int GetReverseDir(int idx) {
	if (idx == 1) return 2;
	if (idx == 2) return 1;
	if (idx == 3) return 4;
	return 3;
}

2. 상어의 속도 (1초에 이동할 수 있는 거리)가 1000 이하의 숫자 이기 때문에 작지 않은 숫자이다. 따라서 작은 숫자로 만들어줄 필요가 있다. 상어의 이동 방향이 위, 아래일 경우 이동 가능 거리는 속도를  (R-1) * 2 로 나눈 나머지이고 오른쪽, 왼쪽일 경우 (C-1) * 2 로 나눈 나머지이다. 여기서 R, C는 지도에 row, column 끝 좌표이다.

int dist = map[i][j].speed; // 상어 이동 가능 거리
// 이동 가능 거리 축소
if (map[i][j].dir <= 2) {
	dist %= ((R - 1) * 2); // 위 아래
}
else dist %= ((C - 1) * 2); // 오른 왼

int r = i, c = j;
while (dist--) {
  int nr = r + dr[map[i][j].dir], nc = c + dc[map[i][j].dir];
  if (nr < 1 || nr > R || nc < 1 || nc > C) {
  	// 벽을 만난 경우 GetReverseDir 함수로 방향 전환
    map[i][j].dir = GetReverseDir(map[i][j].dir);
    nr = r + dr[map[i][j].dir], nc = c + dc[map[i][j].dir];
}
r = nr, c = nc;

3. 상어가 한 장소에 2마리 이상 존재 할 수 있으므로 map과 크기가 같은 tmp 배열로 이동하고 tmp 배열을 다시 map 배열에 복사해주는 과정이 필요하다. 그리고 상어의 크기가 가장 큰 녀석이 나머지 상어들을 잡아 먹으므로 크기가 가장 큰 상어만 저장하면 된다.

// 만약 이미 상어가 있다면 가장 큰 상어만 저장
if (tmp[r][c].body != 0) { 
  if (map[i][j].body > tmp[r][c].body) 
  tmp[r][c] = map[i][j];
}
else tmp[r][c] = map[i][j];

 

코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int R, C, M;
struct INFO {
	int speed, dir, body;
};
INFO map[101][101];
const int dr[] = { 0,-1,1,0,0 };
const int dc[] = { 0,0,0,1,-1 };

int Fishing(int pos) {
	int ret = 0;
	for (int i = 1; i <= R; i++) {
		if (map[i][pos].body != 0) {
			ret = map[i][pos].body;
			map[i][pos] = { 0,0,0 };
			break;
		}
	}
	return ret;
}

int GetReverseDir(int idx) {
	if (idx == 1) return 2;
	if (idx == 2) return 1;
	if (idx == 3) return 4;
	return 3;
}

void Moving() {
	INFO tmp[101][101] = { 0, };
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			if (map[i][j].body != 0) {
				int dist = map[i][j].speed;

				if (map[i][j].dir <= 2) {
					dist %= ((R - 1) * 2);
				}
				else dist %= ((C - 1) * 2);

				int r = i, c = j;
				while (dist--) {
					int nr = r + dr[map[i][j].dir], nc = c + dc[map[i][j].dir];
					if (nr < 1 || nr > R || nc < 1 || nc > C) {
						map[i][j].dir = GetReverseDir(map[i][j].dir);
						nr = r + dr[map[i][j].dir], nc = c + dc[map[i][j].dir];
					}
					r = nr, c = nc;
				}
				if (tmp[r][c].body != 0) {
					if (map[i][j].body > tmp[r][c].body)
						tmp[r][c] = map[i][j];
				}
				else tmp[r][c] = map[i][j];
			}
		}
	}
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			map[i][j] = tmp[i][j];
		}
	}
}

int main() {
	int ans = 0;
	scanf("%d %d %d", &R, &C, &M);
	for (int i = 0; i < M; i++) {
		int r, c;
		scanf("%d %d", &r, &c);
		scanf("%d %d %d", &map[r][c].speed, &map[r][c].dir, &map[r][c].body);
	}
	for (int pos = 1; pos <= C; pos++) {
		ans += Fishing(pos);
		Moving();
	}
	printf("%d", ans);
	return 0;
}

 

아쉬운 점

1. 이동 가능한 거리가 1000이하의 숫자라는 점에서 이동 한 위치를 어떻게 바로 구할 수 있을지 생각하는데 오래 걸렸다. 현재 위치에서 다시 제자리로 돌아오기 위해서는 위, 아래의 경우 (R-1)*2, 오른, 왼의 경우 (C-1)*2 칸 만큼 이동했을 때라는 것을 생각해 나머지 연산으로 이동 거리를 축소 시킬 수 있었다. 허나 다른 풀이를 찾아보니 한 번에 다음 위치를 결정할 수 있도록 계산한 풀이들을 볼 수 있었다. 만약 내 방법대로 했을 때도 시간 초과가 나왔을 경우 한 번에 다음 위치를 계산할 수 있는 방법을 생각해내야 한다.