글 읽기 - 예제는 잘 출력되는데 틀렸습니다.

chlqjarbs 5년 전 0

예제는 잘 출력되는데 어느 부분이 틀렸는지 잘 모르겠습니다.

실패 케이스라도 알려주시면 감사하겠습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        String[][] map = new String[M+1][N+1];

        for (int i=1; i<=M; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j=1; j<=N; j++) {
                map[i][j] = Integer.toBinaryString(Integer.parseInt(st.nextToken()));
            }
        }
        CastleWall castleWall = new CastleWall(map);
        System.out.println(castleWall.roomCount());
        System.out.println(castleWall.maxRoomArea());
        System.out.println(castleWall.sumRoomArea());
        br.close();
    }
                                //8, 4, 2, 1
    static class CastleWall {   //남, 동, 북, 서
        private final int[] Y = {0, 1, 0, -1};
        private final int[] X = {1, 0, -1, 0};
        private String[][] map;
        private int[][] room;
        private ArrayList<Integer> roomSize = new ArrayList<>();

        public CastleWall(String[][] map) {
            this.map = map;
        }

        public int roomCount() {
            int N = map[0].length;
            int M = map.length;
            boolean[][] visited = new boolean[M][N];
            room = new int[M][N];
            int count = 1;
            for (int i=1; i<M; i++) {
                for (int j=1; j<N; j++) {
                    if (room[i][j] == 0) {
                        roomSize.add(bfs(visited, room, count++, i, j));
                    }
                }
            }
            int max = Integer.MIN_VALUE;
            for (int i=1; i<M; i++) {
                for (int j=1; j<N; j++) {
                    max = Math.max(max, room[i][j]);
                }
            }
            return max;
        }

        private int bfs(boolean[][] visited, int[][] room, int count, int x, int y) {
            Queue<Pair> queue = new LinkedList<>();
            int N = map[0].length;
            int M = map.length;
            queue.offer(new Pair(x, y));
            visited[x][y] = true;
            room[x][y] = count;
            int size = 1;

            while (!queue.isEmpty()) {
                Pair pair = queue.poll();
                char[] wall = makeFourDigits(map[pair.getX()][pair.getY()]).toCharArray();
                for (int i=0; i<4; i++) {
                    if (wall[i] == '0') {
                        int adj_x = pair.getX() + X[i];
                        int adj_y = pair.getY() + Y[i];
                        if (adj_x > 0 && adj_y > 0 && adj_x < M && adj_y < N) {
                            if (!visited[adj_x][adj_y]) {
                                visited[adj_x][adj_y] = true;
                                room[adj_x][adj_y] = count;
                                queue.offer(new Pair(adj_x, adj_y));
                                size++;
                            }
                        }
                    }
                }
            }
            return size;
        }

        private String makeFourDigits(String wall) {
            StringBuilder sb = new StringBuilder();
            if (wall.length() < 4) {
                int n = 4 - wall.length();
                for (int i=0; i<n; i++) {
                    sb.append('0');
                }
            }
            sb.append(wall);
            return sb.toString();
        }

        public int maxRoomArea() {
            return Collections.max(roomSize);
        }

        public int sumRoomArea() {
            Queue<Pair> queue = new LinkedList<>();
            int N = map[0].length;
            int M = map.length;
            int max = Integer.MIN_VALUE;
            boolean[][] visited = new boolean[M][N];
            visited[1][1] = true;
            queue.offer(new Pair(1, 1));

            while (!queue.isEmpty()) {
                Pair pair = queue.poll();

                for (int i=0; i<4; i++) {
                    int adj_x = pair.getX() + X[i];
                    int adj_y = pair.getY() + Y[i];
                    if (adj_x > 0 && adj_y > 0 && adj_x < M && adj_y < N) {
                        int n1 = room[pair.getX()][pair.getY()];
                        int n2 = room[adj_x][adj_y];
                        if (!visited[adj_x][adj_y]) {
                            if (n1 != n2) {
                                int sum = roomSize.get(n1-1) + roomSize.get(n2-1);
                                max = Math.max(max, sum);
                            }
                            visited[adj_x][adj_y] = true;
                            queue.offer(new Pair(adj_x, adj_y));
                        }
                    }
                }
            }
            return max;
        }
    }

    static class Pair {
        private int x, y;

        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public int getX() {
            return x;
        }

        public int getY() {
            return y;
        }
    }
}

이 문제는 되게 스트레스 받게 되는 문제네요.. 저도 틀려서 문제 원본을 한 번 찾아보니 (http://gooddaytocode.blogspot....) 원본 문제는 요구하는 입력 및 출력값이 BOJ 에 있는 내용과 조금 다르네요. 그래서, BOJ 에 맞게 입력값 (n,m 위치 변경) 변경해서 공개된 답안으로 출력한 결과값이랑 비교해봤는데, 같은 결과값이 나왔는데도,

틀렸다고 나오네요.. -_-; BOJ 에서 추가한 TC 에서 fail 이 발생하는 것인지.. 음..

첨부 tc 랑 답이랑 한 번 비교해보시겠어요? 잘 되시나요?

YUBgorithm 4년 전 1

위에 첨부된 마지막 50*50 테케

답이

27 55 85 가 아니라

306 905 1233가 나오면 맞네요

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

문제

문제

출처

ICPC

예제는 잘 출력되는데 틀렸습니다.

chlqjarbs 5년 전 0

sgchoi5 5년 전 0

YUBgorithm 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말