반응형
문제 제대로 안 읽고 오름차순인거 캐치 못하고 계속 삽질..
나는 왜그럴까..
import java.io.File;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Deque;
import java.util.List;
import java.util.Scanner;
public class Main {
static boolean[][] isChecked; //체크여부
static int[][] map; //지도
static int mapSize; //지도의 크기
static Deque<int[]> queue = new ArrayDeque<>(); //방문할 좌표
static int[] xmove = new int[]{-1, 1, 0, 0}; //상하좌우
static int[] ymove = new int[]{0, 0, -1, 1}; //상하좌우
static int townCnt = 0;
public static void main(String[] args) throws Exception{
Scanner sc = new Scanner(System.in);
mapSize = Integer.parseInt(sc.nextLine());
map = new int[mapSize][mapSize];
isChecked = new boolean[mapSize][mapSize];
//map 저장
for(int i=0; i<mapSize; i++){
String row = sc.nextLine();
for(int j=0; j<row.length(); j++){
map[i][j] = row.charAt(j) - '0';
}
}
for(int i=0; i<mapSize; i++){
for(int j=0; j<mapSize; j++){
if(!isChecked[i][j] && map[i][j] == 1){ //방문체크 안되어있는 1값인 경우 시작
townCnt += 1; //단지 카운트
bfs(i, j);
}
}
}
System.out.println(townCnt);
Collections.sort(townSizes);
for(Integer cnt : townSizes){
System.out.println(cnt);
}
}
static List<Integer> townSizes = new ArrayList<>();
public static void bfs(int x, int y){
int townSize = 1;
queue.add(new int[]{x, y});
isChecked[x][y] = true;
while(!queue.isEmpty()){
int[] position = queue.poll();
for(int i=0; i<4; i++){
int newx = position[0] + xmove[i];
int newy = position[1] + ymove[i];
if(newx >= 0 && newy >= 0 && newx < mapSize && newy < mapSize
&& map[newx][newy] == 1
&& !isChecked[newx][newy]
){
queue.add(new int[]{newx, newy});
isChecked[newx][newy] = true;
townSize += 1;
}
}
}
townSizes.add(townSize);
}
}
반응형
'코딩 관련 > 코딩문제풀기' 카테고리의 다른 글
[백준] 부분합 (0) | 2024.11.14 |
---|---|
[백준] 세 수 java (0) | 2024.11.14 |
[백준] 바이러스 java (0) | 2024.11.12 |
[백준] 미로탐색 java (0) | 2024.11.07 |
[백준] 보석 도둑 java (0) | 2024.10.30 |