[Algorithm][C++] BOJ 19237 어른 상어

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

19237번: 어른 상어

 

풀이 핵심

1. 구현 / 시뮬레이션 문제

 

2. 상어의 위치, 방향, 우선 순위 방향 정보를 저장하는 shark 배열을 만든다. (배열의 인덱스가 상어의 고유 번호 이다.)

 

3. 상어가 죽었다는 것은 상어의 방향이 -1일 경우로 한다. M 개의 상어를 탐색하며 상어의 현재 자리에 냄새를 남긴다. 냄새는 smell 배열에 상어의 고유 번호, 현재 시간 정보를 저장한다. 이 때 현재 시간 정보를 저장하는 이유는 나중에 탐색했을 때 현재 시간 - smell[r][c].time 이 k보다 크거나 같으면 냄새가 사라졌다고 판단하기 위함이다.

 

4. 상어의 위치를 옮기기 위한 temp[20][20] 배열을 0으로 초기화해서 생성한다. 먼저 빈 칸으로 들어갈 수 있는지 우선순위 방향 순서로 탐색해서 찾는다. 만약 빈 칸을 찾았다면 move_flag를 true로 바꿔 다음 상어를 이동 시킬 수 있도록 한다. 여기서 중요한 점은 상어가 빈 칸을 찾았는데 temp 배열에 다른 상어가 들어가 있다면 상어의 고유 번호 (인덱스) 크기를 비교해 번호가 큰 상어를 없엔다. 빈 칸을 찾지 못했다면 (move_flag가 여전히 false 라면) 주변 중에 내가 냄새를 남긴 곳을 우선 순위 방향 순서로 탐색해서 들어간다.

 

5. 이를 상어가 하나 남을 때까지 반복한다. 만약 시간이 1000이 넘게 되면 루프를 빠져나오고 -1를 return 한다.

 

코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int n, m, k;
int map[20][20];
struct SHARK {
	int r, c, d; // 상어의 위치, 방향
	int priority_dir[4][4]; // 상어의 우선 순위 방향 순서
};
SHARK shark[201];

// 위, 아래, 왼쪽, 오른쪽
const int dr[] = { -1,1,0,0 };
const int dc[] = { 0,0,-1,1 };

struct SMELL { // 상어의 고유 번호, 시간
	int id, time;
};
SMELL smell[20][20]; // 상어의 냄새를 저장하는 배열

int get_time() {
	int ret = -1; // ret은 현재 시간
	int shark_size = m;
	
	while (shark_size > 1 && ret != 1000) { // 상어가 한마리 남거나 시간이 1000보다 클 때 루프 종료
		++ret;
        
        // 상어 냄새 남기기
		for (int idx = 1; idx <= m; idx++) {
			SHARK cur = shark[idx];
			if (cur.d == -1) continue; // 상어의 방향 정보가 -1이면 죽은 것
			smell[cur.r][cur.c].id = idx;
			smell[cur.r][cur.c].time = ret;
		}
        
        // 상어 이동하기
		int temp[20][20] = { 0, }; // 상어를 임시로 이동할 배열
		for (int idx = 1; idx <= m; idx++) {
			SHARK& cur = shark[idx];
			if (cur.d == -1) continue; // 상어의 방향 정보가 -1이면 죽은 것
			int nr, nc, nd; // 다음 행/열 위치, 다음 방향
			bool move_flag = false; // 빈 칸으로 이동했는지 확인용
            
            // 빈 칸 탐색
			for (int i = 0; i < 4; i++) {
				nd = cur.priority_dir[cur.d][i];
				nr = cur.r + dr[nd];
				nc = cur.c + dc[nd];
				if (nr < 0 || nr >= n || nc < 0 || nc >= n ||\
					(smell[nr][nc].id && (ret - smell[nr][nc].time) < k)) continue;
                
                // 빈 칸을 찾았지만 그 곳에 다른 상어가 이동 했었다면 번호 크기 비교
				if (temp[nr][nc]) {
					if (temp[nr][nc] > idx) {
						int die_idx = temp[nr][nc];
						temp[nr][nc] = idx;
						shark[die_idx].d = -1;
					}
					else {
						cur.d = -1;
					}
					--shark_size;
				}
				else {
					temp[nr][nc] = idx;
					cur.r = nr, cur.c = nc, cur.d = nd;
				}
				move_flag = true;
				break;
			}

			if (move_flag) continue;
			
            // 상어가 빈 칸으로 이동하지 못했다면
			for (int i = 0; i < 4; i++) {
				nd = cur.priority_dir[cur.d][i];
				nr = cur.r + dr[nd];
				nc = cur.c + dc[nd];
				if (nr < 0 || nr >= n || nc < 0 || nc >= n ||\
					smell[nr][nc].id != idx) continue;
				temp[nr][nc] = idx;
				cur.r = nr, cur.c = nc, cur.d = nd;
				break;
			}
		}
        
        // temp 배열 map으로 복사
		for (int r = 0; r < n; r++) {
			for (int c = 0; c < n; c++) {
				map[r][c] = temp[r][c];
			}
		}
	}
    
    // 시간이 1000 초과 했다면 -1 return
	if (ret == 1000) return -1;
	return ret + 1; // 더하기 1 해주는 이유는 반복문 종료 조건을 확인하는 것이 루프의 시작이기 때문
}

int main() {
	scanf("%d %d %d", &n, &m, &k);
	for (int r = 0; r < n; r++) {
		for (int c = 0; c < n; c++) {
			scanf("%d", &map[r][c]);
			if (map[r][c]) {
				shark[map[r][c]].r = r;
				shark[map[r][c]].c = c;
			}
		}
	}
	for (int i = 1; i <= m; i++) {
		int tmp;
		scanf("%d", &tmp);
		--tmp; // 방향 인덱스가 0부터 시작하므로
		shark[i].d = tmp;
	}
	for (int i = 1; i <= m; i++) {
		for (int dir = 0; dir < 4; dir++) {
			for (int j = 0; j < 4; j++) {
				int tmp;
				scanf("%d", &tmp);
				--tmp; // 방향 인덱스가 0부터 시작하므로
				shark[i].priority_dir[dir][j] = tmp;
			}
		}
	}
	int ret = get_time();
	printf("%d", ret);
	return 0;
}

 

아쉬운점

오랜만에 알고리즘 문제를 풀다보니 풀이가 조금 지저분해 진 것 같다.

꾸준히 하루에 하나씩은 문제를 풀도록 해야겠다.