728x90
문제 링크
문제 설명
치즈덩어리가 가장 많을 때의 덩어리 개수 구하기
치즈덩어리(상, 하, 좌, 우로 인접한 칸들을 하나로 묶어놓은 것)
입력
첫 번째 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스의 첫 번째 줄에는 치즈의 한 변의 길이 N(2 ≤ N ≤ 100)이 주어진다.
이어서 N개의줄에 걸쳐서 각 칸의 맛있는 정도가 1부터 100 사이의숫자로 주어진다.
출력
각 테스트 케이스마다 ‘#x’(x는 테스트케이스번호를 의미하며 1부터 시작한다)를 출력하고,
각 테스트 케이스마다 100일 중에서 가장 덩어리가 많을 때의 덩어리 개수를 출력하라.
구조화
"X번째날에는 맛있는 정도가 X인 칸을 먹어버린다."고 하여
0부터 입력받은 최고값까지 for문을 돌리고,
해당 값보다 큰 경우만 bfs돌게끔 하여 치즈덩어리 개수 파악
소스 코드
import java.io.*;
import java.util.*;
public class Solution {
static int T, N;
static int[][] cheeze;
static boolean[][] visited;
// 상하좌우
static int[][] way = {{-1,0},{1,0},{0,-1},{0,1}};
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
T = Integer.parseInt(br.readLine());
for (int t = 1; t <= T; t++)
{
int max = Integer.MIN_VALUE;
int cnt = 0;
int result = 0;
N = Integer.parseInt(br.readLine());
cheeze = new int[N][N];
visited = new boolean[N][N];
for (int i = 0; i < N; i++)
{
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++)
{
cheeze[i][j] = Integer.parseInt(st.nextToken());
max = Math.max(max, cheeze[i][j]);
}
}
for (int i = 0; i <= max; i++)
{
cnt = 0;
visited = new boolean[N][N];
for (int r = 0; r < N; r++)
{
for (int c = 0; c < N; c++)
{
if(cheeze[r][c] > i && !visited[r][c])
{
bfs(r,c,i);
cnt++;
}
}
}
result = Math.max(result, cnt);
}
System.out.printf("#%d %d%n",t,result);
}
}
private static void bfs(int r, int c, int num) {
Queue<int[]> q = new LinkedList<int[]>();
q.add(new int[] { r, c });
while (!q.isEmpty()) {
int[] cur = q.poll();
int cr = cur[0];
int cc = cur[1];
visited[r][c] = true;
for (int i = 0; i < 4; i++) {
int nr = cr + way[i][0];
int nc = cc + way[i][1];
if (nr >= 0 && nc >= 0 && nr < N && nc < N) {
if (!visited[nr][nc] && cheeze[nr][nc] > num) {
q.add(new int[] { nr, nc });
visited[nr][nc] = true;
}
}
}
}
}
}
'Algorithm > SWEA' 카테고리의 다른 글
SWEA 1227 미로2(JAVA) 😵 (0) | 2022.11.27 |
---|---|
SWEA 4193 수영대회 결승전(JAVA) 🏊♀️ (0) | 2022.11.20 |
SWEA 2112 보호 필름(JAVA) 📱 (0) | 2022.11.20 |
SWEA 1486 장훈이의 높은 선반(JAVA) ↑ (2) | 2022.11.13 |
SWEA 5656 벽돌 깨기(JAVA) 🔨 (0) | 2022.10.09 |