728x90
반응형
문제
https://www.acmicpc.net/problem/20058
풀이 방법
풀이 순서를 차분하게 정하고 코드로 구현만 한다면 생각보다 간단한 문제였다.
1. 우선 처음에 해야하는건 부분 격자로 나누고, 그 안에 있는 요소를 시계방향으로 회전 시켜준다.
2. 주변에 얼음이 없는 칸을 찾고, 만약 얼음이 없는 칸이 3개 미만이면 해당 위치의 얼음의 개수를 -1 해준다.
여기서 주의해야할 점이 얼음의 개수를 바로바로 업데이트해주면 안된다.
1 2 4
1 3 4
3 4 5
이런 형태에서 얼음을 제거할때 만약 얼음의 개수를 바로바로 적용을 시켜준다면 결과가 원하는대로 나오지 않는다. 만약 바로 적용시켜준다면
0 2 3
0 3 4
2 4 4
이런 형태가 될텐데 이렇게 하면 제대로 정답이 나오지 않고, 제대로 정답이 나오기 위해선
0 2 3
1 3 4
2 3 4
이런 형태가 되도록 구현해야한다.
3. 1, 2번을 Q번 반복한 뒤에는 얼음의 총합과 얼음의 가장 큰 덩어리가 차지하는 칸의 개수를 구해주면 된다.
나는 얼음의 총합은 미리 구해놓고, 얼음을 제거해줄때마다 같이 줄여주는 식으로 구현했다.
얼음의 덩어리는 dfs를 사용해서 구해주면 된다. 여기서 실수했던점이 얼음이 있을 때에만 bfs를 시작해야했는데 그걸 빠뜨려서 처음에 제대로 답이 나오지 않았다. 금방 찾아서 다행...
제출 코드
import java.io.*;
import java.util.*;
public class BOJ_20058_마법사상어와파이어스톰 {
static int[][] move = {{0,1},{0,-1},{1,0},{-1,0}};
static int[][] map;
static int sum;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int Q = Integer.parseInt(st.nextToken());
int n = (int) Math.pow(2, N); //전제 길이
map =new int[n][n];
int[] list_l = new int[Q]; // L의 리스트
sum=0; //전체 얼음 개수
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < n; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
sum+= map[i][j];
}
}
st = new StringTokenizer(br.readLine());
for (int i = 0; i < Q; i++) {
list_l[i] = Integer.parseInt(st.nextToken());
}
//Q만큼 실행
for (int i = 0; i < Q; i++) {
rotate(list_l[i]); //회전 시키기
clearIce(); //조건에 따라 얼음 제거
}
//남아있는 얼음의 양
System.out.println(sum);
//가장 큰 덩어리의 칸 수
System.out.println(kan());
}
static void rotate(int l) { //l길이의 구역을 90도 회전
int[][] copy = new int[map.length][map.length];
for (int i = 0; i < map.length; i++) {
copy[i] = Arrays.copyOf(map[i], map.length);
}
int nl = (int) Math.pow(2, l); //부분격자의 길이
for (int i = 0, j=0; j < map.length; ) {
//시작점을 기준으로 시계방향으로 90도 회전
for (int p = 0; p < nl; p++) {
for (int q = 0; q < nl; q++) {
map[i+q][j+nl-p-1]= copy[i+p][j+q];
}
}
i+= nl; //격자 길이만큼 시작점 행 인덱스에 추가
if(i>map.length-1) { //범위 벗어나면 열에 격자길이만큼 추가 후 행의 다시 0으로
i=0;
j+= nl;
}
}
}
static void clearIce() { //
int[][] copy = new int[map.length][map.length];
for (int i = 0; i < map.length; i++) {
copy[i] = Arrays.copyOf(map[i], map.length);
}
for (int i = 0; i < map.length; i++) {
for (int j = 0; j < map.length; j++) {
if(map[i][j] > 0) { //현재 위치의 얼음이 0보다 큰 경우에만
int cnt=0;
for (int k = 0; k < 4; k++) { //인접한 구역에 얼음이 있는지 확인
int ni = i+move[k][0];
int nj = j+move[k][1];
if(ni>=0 && ni<map.length && nj>=0 && nj<map.length && copy[ni][nj]>0) {
cnt++;
}
}
if(cnt < 3) { //얼음이 있는 구역이 3개미만인 경우 얼음 제거
map[i][j]--;
sum--; //전체 얼음 개수도 -1
}
}
}
}
}
private static int kan() { //큰 덩어리의 칸 개수 구하기
int ans = 0;
int n = map.length;
boolean[][]visit = new boolean[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if(!visit[i][j] && map[i][j]>0) { //아직 방문안하고, 얼음이 있는 경우
int cnt=0;
Queue<int[]> que = new LinkedList<int[]>();
que.add(new int[] {i, j});
visit[i][j] = true;
while(!que.isEmpty()) { //bfs로 얼음의 덩어리가 차지하는 칸의 개수 구하기
int[] temp = que.poll();
cnt++;
for (int k = 0; k < 4; k++) {
int ni= temp[0]+move[k][0];
int nj= temp[1]+move[k][1];
if(ni>=0 && ni<map.length && nj>=0 && nj<map.length && map[ni][nj]>0 && !visit[ni][nj]) {
que.offer(new int[] {ni,nj});
visit[ni][nj] = true;
}
}
}
ans = Math.max(ans, cnt); //가장 큰 칸의 개수로 업데이트
}
}
}
return ans;
}
}
728x90
반응형
'알고리즘 > BJ' 카테고리의 다른 글
[BJ] 백준 11047 동전 0 (JAVA) (0) | 2022.06.27 |
---|---|
[BJ] 백준 21610 마법사 상어와 비바라기 (JAVA) (0) | 2022.06.22 |
[BJ] 백준 2579 계단 오르기 (JAVA) (0) | 2022.04.20 |
[BJ] 백준 2748 피보나치 수2 (JAVA) (0) | 2022.04.13 |
[BJ] 백준 1003 피보나치 함수 (JAVA) (0) | 2022.04.12 |