[BOJ] 2933번 : 미네랄

https://www.acmicpc.net/problem/2933

2933번: 미네랄

 

복잡한 구현 문제다.

 

문제 서술이 조금 빈약한 점이 있는데, 클러스터가 떨어질 때에는 무조건 아랫 면이 다른 클러스터와 닿아야 멈출 수 있다. 예를 들어 예제 3번을 보면 ㄱ자 클러스터가 떨어지는 와중에 오른쪽 면이 다른 클러스터와 닿는 경우가 생기는데, 이때는 멈추지 않는다.

이런 느낌이다.

 

따라서 다음의 생각을 가지고 해결하면 된다.

 

1. 모든 클러스터는 바닥과 연결되어 있어야 한다. 

• BFS로 체크한다. 단, 모든 클러스터를 확인할 필요는 없고 방금 부순 미네랄 위, 옆, 아래만 확인하면 된다.

2. 연결이 안 되어 있으면 공중에 떠 있는 클러스터를 바닥에 닿을 때까지 한 칸씩 내려준다.

• 바닥의 연결은 굳이 BFS를 쓸 필요는 없다. 모든 블럭을 한 칸씩 내려줄 때 바닥과 닿거나 다른 클러스터와 닿는지 확인한다.

bool fall() {
    bool ground = false;

    for(int i = r; i > 0; i--) {
        for(int j = 1; j <= c; j++) {
            if(chk[i-1][j]) {
                chk[i-1][j] = false;
                chk[i][j] = true;
                map[i-1][j] = '.';
                map[i][j] = 'x';
                if((i+1 <= c && map[i+1][j] == 'x' && chk[i+1][j] == false) || i==r) {
                    ground =true;
                }
            }
        }
    }

    return ground;
}

난 위와 같이 구현했다. if문에서 한 칸 밑이 다른 클러스터 OR 내려준 칸이 바닥인지 확인한다. 참이라면 바닥과 닿아있게 된다.

 

시간복잡도는 던진 횟수 $100$ 클러스터 떨어뜨리기 $100^3 $, 그리고 하나 부술 때마다 세 번씩 BFS니까 $3 \times O(V+E) \sim 100^2$다.

 

대충 $100\times(100^3+100^2) \sim 10^8$정도 나오는데, 테스트케이스가 그렇게 크진 않아서 무난히 AC를 받을 수 있다..

 

---

한 가지 유의할 점은.. 나는 한 미네랄이 부서졌을 때 위와 옆으로만 분리될 수 있다고 생각했다. 그런데 아래로도 분리되는 경우가 있으니 세 방향 모두 체크하지 않으면 9%에서 WA가 뜬다. 

---

 

전체 코드는 내 github에서 확인할 수 있다.

 

https://github.com/Jordano-Jackson/PS/blob/main/BOJ/2933/2933.cpp 

GitHub - Jordano-Jackson/PS: Problem solving

 

---

References

Footnotes