[백준] 19236 청소년 상어

문제 주소 : www.acmicpc.net/problem/19236

19236번: 청소년 상어

문제 확인

 

시뮬레이션 문제입니다. dfs방식으로 주어진 방식대로 풀어주면 간단하게 풀 수 있습니다.

주의해야 할 점은 dfs 단계마다 맵 정보를 기록 해 두어야 정확한 답을 구할 수 있습니다.

 

풀이

 

방향 전환에 필요한 dx, dy 배열을 선언하고 정해진 물고기의 번호 순서대로 움직여야 하므로 해쉬 기법을 사용합니다.

dfs 단계마다 맵 정보를 기록하기 위해 임시 배열을 선언하고 기록 해 두어 하나의 깊이 탐색이 끝나고 전 단계로 돌아오게 되면 기록 된 정보를 불러와 사용합니다.

모듈러 연산은 많은 시간이 소요되므로 방향의 수가 8 : 2의 배수인 특징을 이용하여 (dir + 1) & 7을 통해 방향전환을 간편하게 할 수 있습니다.

 

코드

#include <cstdio>
#include <string.h>
using namespace std;
typedef struct hsh {
    short x, y, dir;
}hsh;
short dx[] = { -1, -1, 0, 1, 1, 1, 0, -1 },//상 왼 하 오
dy[] = { 0, -1, -1, -1, 0, 1, 1, 1 };
short map[4][4], mx = -1;
hsh hs[17];
void dfs(short x, short y, short val) {
    short cur_dir = hs[map[x][y]].dir, tmp_map[4][4];
    hsh tmp_hs[17];
    hs[map[x][y]].dir = -1;
    val += map[x][y];
    map[x][y] = 0;//상어가 현재 위치 물고기를 먹음
    for (int i = 1; i < 17; ++i) {
        if (hs[i].dir == -1)continue;
        short &fx = hs[i].x, &fy = hs[i].y, &fd = hs[i].dir;
        while (fx + dx[fd] < 0 || 3 < fx + dx[fd] || fy + dy[fd] < 0 || 3 < fy + dy[fd] ||
            (fx + dx[fd] == x && fy + dy[fd] == y))//움직일 수 있는 방향 선택
            fd = (fd + 1) & 7;// 6 & 7 = 6, 7 & 7 = 7, 8 & 7 = 0 임을 이용
        hs[map[fx + dx[fd]][fy + dy[fd]]] = { fx, fy, hs[map[fx + dx[fd]][fy + dy[fd]]].dir };
        map[fx][fy] = map[fx + dx[fd]][fy + dy[fd]];
        fx += dx[fd] ,fy += dy[fd];
        map[fx][fy] = i;//정보, 맵 수정
    }
    memcpy(tmp_map, map, sizeof(tmp_map));//정보 기록
    memcpy(tmp_hs, hs, sizeof(tmp_hs));
    for (x += dx[cur_dir],  y += dy[cur_dir]; ; x += dx[cur_dir], y += dy[cur_dir]) {
        if(0 <= x && x < 4 && 0 <= y && y < 4){
            if (!map[x][y]) {//빈칸인 경우
                mx = val > mx ? val : mx;
            }
            else {
                dfs(x, y, val);
                memcpy(map, tmp_map, sizeof(tmp_map));//탐색이 끝나면 정보 복구
                memcpy(hs, tmp_hs, sizeof(tmp_hs));
            }
        }
        else {//맵 밖의 경우
            mx = val > mx ? val : mx;
            break;
        }
    }
}
int main() {
    for (short i = 0; i < 4; ++i)
        for (short j = 0; j < 4; ++j) {
            short dir;
            scanf("%hd%hd", &map[i][j],&dir);
            hs[map[i][j]] = { i, j, --dir };
        }
    dfs(0, 0, 0);
    printf("%hd", mx);
}