글 읽기 - TreeSet은 틀리고 ArrayList는 정답인지 모르겠습니다.

jeongyong95 3년 전 0

아래 코드는 맞았습니다.

정렬된 값을 출력하면 된다는 것에 착안하여 처음에는 bfs 함수의 리턴 값을 Set(TreeSet)으로 받았습니다.

테스트 케이스도 통과했고, 로직이 맞으니까 체점을 돌렸는데 16%에서 틀리더라구요.

같은 로직에서 반환값을 Set에서 List로 바꾸고 42번째 줄에 정렬을 해서 맞았는데 treeSet을 사용하면 왜 틀리는지 모르겠습니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Solution2583 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());

        int m = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        int[][] map = new int[m][n];

        while (k-- > 0) {
            st = new StringTokenizer(br.readLine());

            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            int x2 = Integer.parseInt(st.nextToken());
            int y2 = Integer.parseInt(st.nextToken());

            for (int i = y; i < y2; i++) {
                for (int j = x; j < x2; j++) {
                    map[i][j] = 1;
                }
            }
        }
        br.close();
        List<Integer> answer = bfs(map);
        Collections.sort(answer);

        bw.write(answer.size() + "\n");
        for (int i : answer) {
            bw.write(i + " ");
        }
        bw.flush();
        bw.close();
    }

    static List<Integer> bfs(int[][] map) {
        List<Integer> answer = new ArrayList<>();
        Queue<int[]> q = new LinkedList<>();
        int[] moveN = { 0, 0, -1, 1 };
        int[] moveM = { -1, 1, 0, 0 };

        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[i].length; j++) {
                if (map[i][j] == 1) {
                    continue;
                }

                int[] start = { i, j };
                int sectionSize = 1;
                q.offer(start);
                map[i][j] = 1;

                while (!q.isEmpty()) {
                    int[] current = q.poll();
                    for (int k = 0; k < 4; k++) {
                        int[] temp = { current[0] + moveN[k], current[1] + moveM[k] };
                        if (temp[0] >= 0 && temp[0] < map.length && temp[1] >= 0 && temp[1] < map[temp[0]].length) {
                            if (map[temp[0]][temp[1]] == 0) {
                                sectionSize++;
                                q.offer(temp);
                                map[temp[0]][temp[1]] = 1;
                            }
                        }
                    }
                }
                answer.add(sectionSize);
            }
        }
        return answer;
    }
}

myoungs14 2년 전 1

같은 크기의 영역이 있을때 반례가 나오는 것 같습니다.

ex 5 1 2 5라는 답이 나왔을때

set는 중복을 제거해서 1 2 5로 나올겁니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

TreeSet은 틀리고 ArrayList는 정답인지 모르겠습니다.

jeongyong95 3년 전 0

myoungs14 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말