[JAVA] 백준 "단지번호붙이기"

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

 

필자의 코드는 계속해서 오답이라고 뜨는데, 모든 반례가 다 알맞게 출력된다.

import java.io.*;
import java.util.*;

class Main {
​​​​static int[][] grid;
​​​​static boolean[][] visited;
​​​​static int[][] vector = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};
​​​​static int count;
​​​​public static void main(String[] args) throws IOException {
​​​​​​​​Scanner sc = new Scanner(System.in);

​​​​​​​​int n = sc.nextInt();
​​​​​​​​grid = new int[n+1][n+1];
​​​​​​​​visited = new boolean[n+1][n+1];
​​​​​​​​for(int j =1; j<n+1; j++){
​​​​​​​​​​​​String temp = sc.next();
​​​​​​​​​​​​for(int i =1; i<n+1; i++){
​​​​​​​​​​​​​​​​grid[j][i] = temp.charAt(i-1) - '0';
​​​​​​​​​​​​}
​​​​​​​​}

​​​​​​​​PriorityQueue<Integer> pq = new PriorityQueue<>();
​​​​​​​​for(int j =1; j<n+1; j++){
​​​​​​​​​​​​for(int i =1; i<n+1; i++){
​​​​​​​​​​​​​​​​if(grid[j][i] == 1 && visited[j][i] == false){
​​​​​​​​​​​​​​​​​​​​count =0;
​​​​​​​​​​​​​​​​​​​​dfs(j, i);//count값
​​​​​​​​​​​​​​​​​​​​pq.offer(count);
​​​​​​​​​​​​​​​​}
​​​​​​​​​​​​}
​​​​​​​​}
​​​​​​​​System.out.println(pq.size());
​​​​​​​​while(!pq.isEmpty()){
​​​​​​​​​​​​System.out.println(pq.poll());
​​​​​​​​}
​​​​}

​​​​//시작점을 변수로 받아 확인, 출력 후 다음 연결점을 찾아 시작점을 변경하여 재호출
​​​​public static void dfs(int j, int i) {
​​​​​​​​int x = i, y = j;
​​​​​​​​visited[j][i] = true;
​​​​​​​​count ++;
​​​​​​​​for (int k = 0; k < 4; k++) {
​​​​​​​​​​​​x += vector[k][0];//+1 -1
​​​​​​​​​​​​y += vector[k][1];//+1 -1
​​​​​​​​​​​​if(x<0||y<0||x>=visited[1].length||y>=visited.length) continue; //overflow방지
​​​​​​​​​​​​if (visited[y][x] == false && grid[y][x] == 1) {
​​​​​​​​​​​​​​​​dfs(y, x);
​​​​​​​​​​​​}
​​​​​​​​​​​​//초기화
​​​​​​​​​​​​x = i;
​​​​​​​​​​​​y = j;
​​​​​​​​}
​​​​}
}

따라서 다른 코드를 살펴보겠다.

 

아래와같다.

import java.util.*;

public class Main {
‌public static void main(String[] args) {
‌‌int[] dy = { -1, 1, 0, 0 };
‌‌int[] dx = { 0, 0, -1, 1 };

‌‌Scanner sc = new Scanner(System.in);
‌‌List<Integer> ans = new ArrayList<>();

‌‌int N = sc.nextInt();
‌‌boolean[][] map = new boolean[N][N];

‌‌for (int i = 0; i < N; i++) {
‌‌‌String input = sc.next();

‌‌‌for (int j = 0; j < N; j++)
‌‌‌‌map[i][j] = input.charAt(j) == '1';
‌‌}

‌‌Queue<int[]> que = new LinkedList<>();
‌‌for (int i = 0; i < N; i++) {
‌‌‌for (int j = 0; j < N; j++) {
‌‌‌‌if (!map[i][j])
‌‌‌‌‌continue;

‌‌‌‌que.add(new int[] { i, j });
‌‌‌‌map[i][j] = false;
‌‌‌‌int size = 0;
‌‌‌‌while (!que.isEmpty()) {
‌‌‌‌‌int[] cur = que.poll();
‌‌‌‌‌size++;

‌‌‌‌‌for (int k = 0; k < 4; k++) {
‌‌‌‌‌‌int ny = cur[0] + dy[k];
‌‌‌‌‌‌int nx = cur[1] + dx[k];

‌‌‌‌‌‌if (ny < 0 || nx < 0 || nx >= N || ny >= N || !map[ny][nx])
‌‌‌‌‌‌‌continue;

‌‌‌‌‌‌que.add(new int[] { ny, nx });
‌‌‌‌‌‌map[ny][nx] = false;
‌‌‌‌‌}
‌‌‌‌}

‌‌‌‌ans.add(size);
‌‌‌}
‌‌}

‌‌System.out.println(ans.size());
‌‌ans.sort(null);
‌‌ans.stream().forEach(System.out::println);

‌}
}

1-7171771.tistory.com/57

백준 2667 단지번호붙이기 java