[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