본문 바로가기
algorithm

백준 21611 - 마법사 상어와 블리자드

오버액션 2025. 1. 27.
728x90

문제 : https://www.acmicpc.net/problem/21611

문제 요약

1. 맵의 가운데에 상어가 있고, 맵은 달팽이 모양으로 이루어져 있다.

2. 맵 가운데의 상어는 먼저 구슬을 s 개 만큼 d 방향으로 파괴한다.

예를들어, 아래와 같이 ↓ 방향으로 2개 만큼 구슬을 파괴할 수 있다.

 

3. 파괴된 이후 구슬을 앞당긴다.

4-1. 구슬 번호가 4개 연속해서 같다면, 구슬의 연쇄 폭발을 발생시킨다.

4-2. 파괴된 이후 구슬을 앞당긴다.

4-3. 폭발이 일어났다면 4-1~2를 반복한다.

5. 구슬을 그룹화 한다. 연속된 번호의 구슬들에 대해 2칸씩 차지하게 되며, 각각 개수, 번호 가 된다.

 

풀이 과정

0. 먼저 맵의 형태가 달팽이 모양이기 때문에, 일반 배열 형태에 매칭시킨 후 진행하는 것이 편리할 것이라고 생각했다.

아래 작업을 통해 0 ~ N*N-1 까지 인덱스들은 달팽이 맵이 이동하는 순서대로 하나씩 매칭되어 있다.

typedef struct option {
    int y,x;
}op;
deque < op > matchedLocations; // matchedLocation[0] = {N/2,N/2}

void matchLocation() {
    int y = N/2, x = N/2;
    int dir = 0;

    matchedLocations.push_back({y,x});
    for(int depth=1; depth<N; depth++) {
        for(int i=0; i<2; i++) {
            for(int j=0; j<depth; j++) {
                y += moveY[dir];
                x += moveX[dir];
                matchedLocations.push_back({y,x});
            }
            dir = (dir+1) % 4;
        }
    }
    for(int i=1; i<N; i++) {
        y += moveY[dir];
        x += moveX[dir];
        matchedLocations.push_back({y,x});
    }
}

 

위 matchedLocations 덱 배열에 실제 달팽이 맵의 위치를 저장한다.

 

1. 이후 구슬을 파괴한 다음 이 문제의 핵심인 구슬 이동 함수를 작성한다.

파괴된 구슬들은 destroyed 배열에 표시하였고, 만약 파괴된 좌표에 다다르면 cnt 를 하나씩 증가시킨다.

이후에 만나는 구슬들은 cnt만큼 칸을 앞당겨주면 된다.

 

여기서 중요한 것은, 만약 구슬이 비어있는 칸을 만났거나, 만나지 못하고 끝났을 경우이다.

 

1-1. 만약 구슬이 비어있는 칸을 만났다면,

그 이전 칸부터 cnt 만큼 비어있는 칸으로 바꿔줘야 한다.

왜냐하면 해당 칸들은 앞당기기만 했을 뿐 이미 기존 값들이 그대로 남아있기 때문이다.

 

예를들어 구슬이 파괴된 후 마지막 구슬 2개는, 위 과정이 없다면 그대로 남아있을 것이다.

 

 

1-2. 만약 구슬이 비어있는 칸을 만나지 않고 끝까지 도달했다면,

마지막 칸 (N*N-1) 부터 cnt 만큼 0으로 비워주는 과정이 필요하다. 

void moveBeads() {
    int y,x;
    int nextIdx,ny,nx;
    int cnt = 0;

    int lastIdx;
    bool flag = false;
    for(int i=1; i<N*N; i++) {
        y = matchedLocations[i].y;
        x = matchedLocations[i].x;
        if(destroyed[y][x]) {
            cnt++;
        }
        else {
            if(space[y][x] >= 1 && cnt != 0) {
                nextIdx = i - cnt;
                ny = matchedLocations[nextIdx].y;
                nx = matchedLocations[nextIdx].x;
                space[ny][nx] = space[y][x];
            }
            else if(space[y][x] == 0) {
                flag = true;
                lastIdx = i-1;
                break;
            }
        }
    }
    // 0인 칸을 만났다면 cnt만큼 0으로 변경
    if(flag) {
        for(int i=lastIdx; i>lastIdx-cnt; i--) {
            y = matchedLocations[i].y;
            x = matchedLocations[i].x;
            space[y][x] = 0;
        }
    }
    // 끝까지 번호로 가득 차 있었다면
    else {
        for(int i=N*N-1; i>N*N-1-cnt; i--) {
            y = matchedLocations[i].y;
            x = matchedLocations[i].x;
            space[y][x] = 0;
        }
    }
}

 

 

2. 이제 연쇄폭발을 발생시킨 다음, 폭발이 일어났다면 위 moveBeads 함수를 통해 이동시켜주고

아니라면 넘어가면 된다.

 

// 3. 연쇄폭발 및 이동
    while(1) {
        if(chainExplode() == 0) break;
        moveBeads();
        memset(destroyed,0,sizeof(destroyed));
    }
    
    ...

int chainExplode() {
    int y,x;
    int ny,nx;
    y = matchedLocations[1].y;
    x = matchedLocations[1].x;
    int nowNum = space[y][x];
    int cnt = 1;
    int chainCnt = 0;
    int lastIdx;
    bool flag = false;

    for(int i=2; i<N*N; i++) {
        y = matchedLocations[i].y;
        x = matchedLocations[i].x;
        if(space[y][x] == 0) {
            lastIdx = i-1;
            flag = true;
            break;
        }
        if(space[y][x] == nowNum) {
            cnt++;
        }
        else {
            if(cnt >= 4) {
                chainCnt++;
                for(int j=i-1; j>i-1-cnt; j--) {
                    ny = matchedLocations[j].y;
                    nx = matchedLocations[j].x;
                    destroyed[ny][nx] = 1;
                }
                explodedBeadsCount(nowNum,cnt);
            }
            nowNum = space[y][x];
            cnt = 1;
        }
    }
    // 빈 칸을 만났을때 4개이상 연속된 상태일 경우
    if(flag && cnt >= 4) {
        chainCnt++;
        for(int i=lastIdx; i>lastIdx-cnt; i--) {
            y = matchedLocations[i].y;
            x = matchedLocations[i].x;
            destroyed[y][x] = 1;
        }
        explodedBeadsCount(nowNum,cnt);
    }
    // 마지막에 도달했을때 4개이상 연속된 상태일 경우
    if(!flag && cnt >= 4) {
        chainCnt++;
        for(int i=N*N-1; i>N*N-1-cnt; i--) {
            y = matchedLocations[i].y;
            x = matchedLocations[i].x;
            destroyed[y][x] = 1;
            explodedBeadsCount(space[y][x],cnt);
        }
        explodedBeadsCount(nowNum,cnt);
    }
    return chainCnt;
}

 

 

3. 마지막으로 그룹화 작업이 필요하다.

그룹화 시에는 기존 구슬들이 영향을 받기 때문에 임시 배열을 선언하여 그룹화된 구슬들을 넣어주고 마지막에 옮겨준다.

void beadGrouping() {
    int y,x;
    int ny,nx;
    y = matchedLocations[1].y;
    x = matchedLocations[1].x;
    int beforeNum = space[y][x];
    int cnt = 1;
    int nowIdx = 1;

    int temp[N][N];
    memset(temp,0,sizeof(temp));

    for(int i=2; i<N*N; i++) {
        y = matchedLocations[i].y;
        x = matchedLocations[i].x;
        if(space[y][x] == beforeNum) {
            cnt++;
        }
        else {
            ny = matchedLocations[nowIdx].y;
            nx = matchedLocations[nowIdx].x;
            temp[ny][nx] = cnt;
            nowIdx += 1;
            if(nowIdx > N*N-1) break;
            ny = matchedLocations[nowIdx].y;
            nx = matchedLocations[nowIdx].x;
            temp[ny][nx] = beforeNum;
            nowIdx += 1;
            if(nowIdx > N*N-1) break;

            if(space[y][x] == 0) break;

            beforeNum = space[y][x];
            cnt = 1;
        }
    }

    for(int i=0; i<N; i++) {
        for(int j=0; j<N; j++) {
            space[i][j] = temp[i][j];
        }
    }
}

 

 

전체 코드

#include <iostream>
#include <deque>
#include <stdio.h>
#include <cstring>
using namespace std;

int N,M;
int answer = 0;
int one = 0, two = 0, three = 0;

int space[50][50];
int destroyed[50][50];

typedef struct option {
    int y,x;
}op;
deque < op > matchedLocations; // matchedLocation[0] = {N/2,N/2}

int dy[4] = {-1,1,0,0};
int dx[4] = {0,0,-1,1};

// 좌 하 우 상
int moveY[4] = {0,1,0,-1};
int moveX[4] = {-1,0,1,0};

void testPrint() {
    printf("\n");
    for(int i=0; i<N; i++) {
        for(int j=0; j<N; j++) {
            printf("%d ",space[i][j]);
        }
        printf("\n");
    }
    printf("\n");
}

void explodedBeadsCount(int now, int cnt) {
    if(now == 1) one += cnt;
    else if(now == 2) two += cnt;
    else if(now == 3) three += cnt;
}

void matchLocation() {
    int y = N/2, x = N/2;
    int dir = 0;

    matchedLocations.push_back({y,x});
    for(int depth=1; depth<N; depth++) {
        for(int i=0; i<2; i++) {
            for(int j=0; j<depth; j++) {
                y += moveY[dir];
                x += moveX[dir];
                matchedLocations.push_back({y,x});
            }
            dir = (dir+1) % 4;
        }
    }
    for(int i=1; i<N; i++) {
        y += moveY[dir];
        x += moveX[dir];
        matchedLocations.push_back({y,x});
    }
}

void destroyBeads(int d, int s) {
    int y = N/2, x = N/2;
    for(int i=0; i<s; i++) {
        y += dy[d];
        x += dx[d];
        destroyed[y][x] = 1;
    }
}

void moveBeads() {
    int y,x;
    int nextIdx,ny,nx;
    int cnt = 0;

    int lastIdx;
    bool flag = false;
    for(int i=1; i<N*N; i++) {
        y = matchedLocations[i].y;
        x = matchedLocations[i].x;
        if(destroyed[y][x]) {
            cnt++;
        }
        else {
            if(space[y][x] >= 1 && cnt != 0) {
                nextIdx = i - cnt;
                ny = matchedLocations[nextIdx].y;
                nx = matchedLocations[nextIdx].x;
                space[ny][nx] = space[y][x];
            }
            else if(space[y][x] == 0) {
                flag = true;
                lastIdx = i-1;
                break;
            }
        }
    }
    // 0인 칸을 만났다면 cnt만큼 0으로 변경
    if(flag) {
        for(int i=lastIdx; i>lastIdx-cnt; i--) {
            y = matchedLocations[i].y;
            x = matchedLocations[i].x;
            space[y][x] = 0;
        }
    }
    // 끝까지 번호로 가득 차 있었다면
    else {
        for(int i=N*N-1; i>N*N-1-cnt; i--) {
            y = matchedLocations[i].y;
            x = matchedLocations[i].x;
            space[y][x] = 0;
        }
    }
}

int chainExplode() {
    int y,x;
    int ny,nx;
    y = matchedLocations[1].y;
    x = matchedLocations[1].x;
    int nowNum = space[y][x];
    int cnt = 1;
    int chainCnt = 0;
    int lastIdx;
    bool flag = false;

    for(int i=2; i<N*N; i++) {
        y = matchedLocations[i].y;
        x = matchedLocations[i].x;
        if(space[y][x] == 0) {
            lastIdx = i-1;
            flag = true;
            break;
        }
        if(space[y][x] == nowNum) {
            cnt++;
        }
        else {
            if(cnt >= 4) {
                chainCnt++;
                for(int j=i-1; j>i-1-cnt; j--) {
                    ny = matchedLocations[j].y;
                    nx = matchedLocations[j].x;
                    destroyed[ny][nx] = 1;
                }
                explodedBeadsCount(nowNum,cnt);
            }
            nowNum = space[y][x];
            cnt = 1;
        }
    }
    // 빈 칸을 만났을때 4개이상 연속된 상태일 경우
    if(flag && cnt >= 4) {
        chainCnt++;
        for(int i=lastIdx; i>lastIdx-cnt; i--) {
            y = matchedLocations[i].y;
            x = matchedLocations[i].x;
            destroyed[y][x] = 1;
        }
        explodedBeadsCount(nowNum,cnt);
    }
    // 마지막에 도달했을때 4개이상 연속된 상태일 경우
    if(!flag && cnt >= 4) {
        chainCnt++;
        for(int i=N*N-1; i>N*N-1-cnt; i--) {
            y = matchedLocations[i].y;
            x = matchedLocations[i].x;
            destroyed[y][x] = 1;
            explodedBeadsCount(space[y][x],cnt);
        }
        explodedBeadsCount(nowNum,cnt);
    }
    return chainCnt;
}

void beadGrouping() {
    int y,x;
    int ny,nx;
    y = matchedLocations[1].y;
    x = matchedLocations[1].x;
    int beforeNum = space[y][x];
    int cnt = 1;
    int nowIdx = 1;

    int temp[N][N];
    memset(temp,0,sizeof(temp));

    for(int i=2; i<N*N; i++) {
        y = matchedLocations[i].y;
        x = matchedLocations[i].x;
        if(space[y][x] == beforeNum) {
            cnt++;
        }
        else {
            ny = matchedLocations[nowIdx].y;
            nx = matchedLocations[nowIdx].x;
            temp[ny][nx] = cnt;
            nowIdx += 1;
            if(nowIdx > N*N-1) break;
            ny = matchedLocations[nowIdx].y;
            nx = matchedLocations[nowIdx].x;
            temp[ny][nx] = beforeNum;
            nowIdx += 1;
            if(nowIdx > N*N-1) break;

            if(space[y][x] == 0) break;

            beforeNum = space[y][x];
            cnt = 1;
        }
    }

    for(int i=0; i<N; i++) {
        for(int j=0; j<N; j++) {
            space[i][j] = temp[i][j];
        }
    }
}

void solution(int d, int s) {
    // 1. 구슬 파괴
    destroyBeads(d,s);

    // 2. 구슬 이동
    moveBeads();
    memset(destroyed,0,sizeof(destroyed));

    // 3. 연쇄폭발 및 이동
    while(1) {
        if(chainExplode() == 0) break;
        moveBeads();
        memset(destroyed,0,sizeof(destroyed));
    }

    // 4. 그룹화
    beadGrouping();
}

int main() {
    int d,s;
    scanf("%d %d",&N,&M);
    for(int i=0; i<N; i++) {
        for(int j=0; j<N; j++) {
            scanf("%d",&space[i][j]);
        }
    }
    // 실제 구슬 좌표를 배열에 매칭
    matchLocation();
    for(int i=0; i<M; i++) {
        scanf("%d %d",&d,&s);
        solution(d-1,s);
    }

    answer += (one) + (two*2) + (three*3);
    printf("%d\n",answer);
}
728x90

'algorithm' 카테고리의 다른 글

백준 19236 - 청소년 상어  (0) 2025.01.05
백준 17825 - 주사위 윷놀이  (1) 2024.12.30
백준 17141 - 연구소 2  (0) 2024.12.10
백준 4179 - 불! (C++)  (0) 2024.11.09
백준 13549 - 숨바꼭질 3  (0) 2024.11.03

'algorithm' 관련글

티스토리툴바