[백준] 20058 - 마법사 상어와 파이어스톰

[백준] 20058 - 마법사 상어와 파이어스톰

[문제링크]

0. 단순 구현 + 그래프 탐색 문제

1. 주어진 l 값에 맞게, 각 칸을 회전시킨다

2. 다른 얼음과 2칸 이하로 맞닿은 칸들을 체크한다

3. 해당 칸들을 녹인다

4. 1~3 반복

5. 다 녹은 후 dfs를 실행, 가장 큰 덩어리의 크기를 찾는다

import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main{ static int[][]map; static boolean[][] chk; static int size; public static void main(String[] args)throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine(), " "); int n = pint(st.nextToken()); int m = pint(st.nextToken()); size = 1<0) { cntMax = Math.max(cntMax, dfs(i,j)); } } } int sum=0; for (int i = 0; i < size; i++) { for (int j = 0; j < size; j++) { sum+=map[i][j]; } } System.out.println(sum+"

"+cntMax); } static int dfs(int x, int y) { int cnt=1; chk[x][y]=true; if(x>0 && !chk[x-1][y] && map[x-1][y]>0)cnt+=dfs(x-1,y); if(y>0 && !chk[x][y-1] && map[x][y-1]>0)cnt+=dfs(x,y-1); if(x0)cnt+=dfs(x+1,y); if(y0)cnt+=dfs(x,y+1); return cnt; } static void divide(int l) { int len = size / (1<0 && map[x-1][y]>0)cnt++; if(y>0 && map[x][y-1]>0)cnt++; if(x0)cnt++; if(y0)cnt++; if(cnt<3 && map[x][y]>0) { chk[x][y]=true; } } } } static void melt() { for (int x = 0; x < size; x++) { for (int y = 0; y < size; y++) { if(chk[x][y])map[x][y]--; } } } static void rotate(int sx, int sy, int len) { if(len<=0)return; int tmp=len-1; int[] backup = new int[tmp]; for (int i = 0; i < tmp; i++)backup[i]=map[sx][sy+i]; for (int i = 0; i < tmp; i++) { map[sx][sy+tmp-1-i]=map[sx+i+1][sy]; } for (int i = 0; i < tmp; i++) { map[sx+i+1][sy]=map[sx+tmp][sy+i+1]; } for (int i = 0; i < tmp; i++) { map[sx+tmp][sy+i+1]=map[sx+tmp-1-i][sy+tmp]; } for (int i = 0; i < tmp; i++) { map[sx+tmp-1-i][sy+tmp]=backup[tmp-1-i]; } rotate(sx+1,sy+1,len-2); } static int pint(String s) { return Integer.parseInt(s); } }

결과 화면

from http://nato-blog.tistory.com/142 by ccl(S) rewrite - 2021-10-26 07:02:40