글 읽기 - 테스트케이스는 다 맞았는데 어느 부분에서 틀린지 모르겠습니다. (주석다수)

gunflake09 4년 전 0

안녕하세요. 연구소 문제 풀다가 반례를 못찾겠습니다.

54퍼정도까지 올라가다가 "틀렸습니다" 메세지가 출력됩니다.

풀이방식은

벽을 세울 곳 3개 재귀로 선택
벽이 3개 세워졌으면, 바이러스 확산 시작
1. 바이러스 확산은 queue로 구현했습니다.
2. 바이러스 확산 후 안전한 지역 출력

3. 구한 벽의 수가 기존의 벽 수보다 크면 교체

이렇게 풀었습니다.

반례를 도저히 못찾겠습니다. 부탁드립니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    //안전한 지역 최대 값
    private static int maxSafePlace = 0;

    private static int [] da ={0,0,-1,1}; //방향 행
    private static int [] db ={1,-1,0,0}; //방향 열

    static class Point{
        int a;
        int b;

        public Point(int a, int b) {
            this.a = a;
            this.b = b;
        }
    }

    public static void main(String[] args) throws IOException {

        //input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine().trim());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int [][] map = new int[N][M];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine().trim());
            for (int j = 0; j < M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        //solve
        solve(map);

        //output
        System.out.println(maxSafePlace);


    }

    private static void solve(int[][] map) {

        //벽 3개 세울것을 선택하기 (DFS)
        chooseWall(map, 0, 0, 0);


    }

    private static void chooseWall(int[][] map, int a, int b, int current) { //a = 행 시작 b = 열 시작
        if(current == 3){ //벽이 3개 세워졌을때 바이러스 확신시작
            //새로운 맵 복사
            int [][] copyMap = copyArray(map);

            //바이러스 확신시작
            int getSafePlace = spreadVirus(copyMap);

            //만약 안전지대공간이 기존보다 크면 교체
            if(getSafePlace>maxSafePlace)
                maxSafePlace = getSafePlace;


            return;
        }else{
            for (int i = a; i < map.length; i++) {
                for (int j = b; j < map[0].length; j++) {
                    if(map[i][j] == 0){
                        map[i][j] = 1; //벽 설치
                        chooseWall(map, a, b+1, current+1);
                        map[i][j] = 0; //백트래킹
                    }
                }
            }
        }
    }

    private static int spreadVirus(int[][] copyMap) {

        //방문 체크 배열
        boolean [][] visit = new boolean[copyMap.length][copyMap[0].length];
        Queue<Point> queue = new LinkedList<>();

        //바이러스인 곳을 찾아서 queue에 넣기
        for (int i = 0; i < copyMap.length; i++) {
            for (int j = 0; j < copyMap[0].length; j++) {
                if(copyMap[i][j] == 2){
                    visit[i][j] = true;
                    queue.add(new Point(i,j));
                }
            }
        }


        while(!queue.isEmpty()){
            Point tmp = queue.poll();

            int ta = tmp.a;
            int tb = tmp.b;

            copyMap[ta][tb] = 2;

            for (int i = 0; i < 4; i++) {
                int nextA = ta+da[i];
                int nextB = tb+db[i];
                //배열 범위 안이고, 방문하지 않았고, 빈칸일 경우 방문
                if(outOfBoundary(copyMap, nextA, nextB) && !visit[nextA][nextB] && copyMap[nextA][nextB] == 0){
                    visit[nextA][nextB] = true;
                    queue.add(new Point(nextA, nextB));
                }
            }
        }

        // 안전한 지역 세기
        int countZero = 0;

        for (int i = 0; i < copyMap.length; i++) {
            for (int j = 0; j < copyMap[0].length; j++) {
                if(copyMap[i][j] == 0)
                    countZero++;
            }
        }

        return countZero;
    }

    //배열 범위 멋어났는지 확인
    private static boolean outOfBoundary(int[][] map, int a, int b){
        if(a>=0 && a<map.length && b>=0 && b<map[0].length)
            return true;
        else
            return false;
    }

    //2차원 배열 복사
    private static int[][] copyArray(int[][] map) {
        int [][] result = new int[map.length][map[0].length];

        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[0].length; j++) {
                result[i][j] = map[i][j];
            }
        }
        return result;
    }
}

gunflake09 4년 전 2

77번째 줄에서 안에 있는 반복문이 끝나면, 시작 위치를 0 으로 바꾸는걸 빼먹어서 틀렸네요.

안에 있는 반복문이끝나면 열 시작위치를 0으로 설정해서 해결했습니다.

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

문제

문제

출처

ICPC

테스트케이스는 다 맞았는데 어느 부분에서 틀린지 모르겠습니다. (주석다수)

gunflake09 4년 전 0

gunflake09 4년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말