글 읽기 - 미네랄2 혹시 30%에서 계속 틀리는데 반례좀 알 수 있을까요 ㅠㅠ

ruddks1001 3년 전 0

30%에서 ㄱㅖ속 틀립니다 ㅠㅠㅠ 아무리 해봐도 안되네요 ㅠㅠ 이틀정도 고민했는데 ㅠㅠ

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.PriorityQueue;

public class Main {
    static char[][]map;
    static int R,C;
    public static void main(String[] args)throws Exception{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
//        BufferedReader bf = new BufferedReader(new FileReader(new File("data.txt")));
        String[] scale = bf.readLine().split(" ");
        R = Integer.parseInt(scale[0]);
        C = Integer.parseInt(scale[1]);
        map = new char[R][C];
        for(int i = 0 ; i < R ; i ++){
            map[i] = bf.readLine().toCharArray();
        }
        int N = Integer.parseInt(bf.readLine());
        String[] tc = bf.readLine().split(" ");
        for(int i = 0 ; i < N ; i ++){
            int height = R - Integer.parseInt(tc[i]);
            int broken ;
            if(i % 2 == 0){
                broken = 0;
                while(broken < R && map[height][broken] != 'x'){
                    broken++;
                }
            }
            else{
                broken = C-1;
                while(broken >= 0 && map[height][broken] != 'x'){
                    broken--;
                }
            }
            if(0 <= broken && broken < R){
                map[height][broken] = '.';
                solve(height,broken);
            }
        }
        print();
    }
    // 메인 solve 함수
    public static void solve(int i,int j){
        int[][] move = {{1,0},{-1,0},{0,1},{0,-1}};
        ArrayList<int[]> block = new ArrayList<>();
        boolean flag = false;
        for(int k = 0 ; k < 4 ; k ++){
            block = new ArrayList<>();
            int curI = i + move[k][0];
            int curJ = j + move[k][1];
            if(0 > curI || 0 > curJ || curI >= R || curJ >= C)continue;
            if(map[curI][curJ] == 'x'){
                block = isChain(curI,curJ);
                if(!block.isEmpty()){ // 만약 리턴받은 block가 비어있으면 땅에 이어져있다는 얘기
                    flag = true;
                    break;
                }
            }
        }
        if(flag) {
            int downNum = down(block);
            for (int[] b : block) {
                map[b[0] + downNum][b[1]] = 'x'; // 0이면 그자리에 x 표기 아니면 그만큼 이동
            }
        }
    }
    // 블럭 이동
    public static int down(ArrayList<int[]> block){
        for(int[] b : block){
            map[b[0]][b[1]] = '.'; // 블럭(클러스터) 이동을 위해 미리 .으로 변경한다 ( 좌표가 있기 때문)
        }
        int answer = 0;
        for(int i = 1 ; i < R ; i ++){
            for(int[] b : block){
                if(b[0]+i >= R || map[b[0]+i][b[1]] == 'x'){
                    answer = i - 1; // 최초로 x 를 만났거나 바닥에 떨어졌을 경우 바로 그 위칸으로 이동해야 하기 때문
                    break;
                }
            }
            if(answer != 0){ // 위 조건에 맞았을 경우 
                break;
            }
        }
        return answer; // 0 이거나 특정 수
    }
    // 떨어져야하는지 바닥에 이어져있는지 검사하는 함수
    public static ArrayList<int[]> isChain(int i, int j){
        if(i == R - 1){
            return new ArrayList<>();
        }
        int[][] move = {{-1,0},{1,0},{0,1},{0,-1}};
        LinkedList<int[]> queue = new LinkedList<>();
        ArrayList<int[]> block = new ArrayList<>();
        queue.add(new int[]{i,j});
        block.add(new int[]{i,j});
        boolean[][] check = new boolean[R][C];
        check[i][j] = true;
        while(!queue.isEmpty()){
            int[] idx = queue.remove();
            for(int k = 0 ; k < 4 ; k ++){
                int curI = idx[0] + move[k][0];
                int curJ = idx[1] + move[k][1];
                if(0 > curI || 0 > curJ || curI >= R || curJ >= C)continue;
                if(check[curI][curJ] || map[curI][curJ] == '.')continue;
                check[curI][curJ] = true;
                block.add(new int[]{curI,curJ});
                if(curI == R-1){
                    return new ArrayList<>();
                }
                queue.add(new int[]{curI,curJ});
            }
        }
        return block;
    }
    // 출력함수
    public static void print(){
        for(char[] mm : map){
            for(char m : mm){
                System.out.print(m);
            }
            System.out.println(" ");
        }
        System.out.println(" ");
    }
}

ruddks1001 3년 전 1

셀프 해결 완료!

테스트한 TC

7 5
.....
.....
.....
.....
.....
.....
.....
2
1 1

8 8
..xxxx..
..x..x..
..x..x..
..x..x..
..x.....
..x.....
..x.....
.xxxxx..
4
2 7 8 1

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

문제

문제

출처

ICPC

미네랄2 혹시 30%에서 계속 틀리는데 반례좀 알 수 있을까요 ㅠㅠ

ruddks1001 3년 전 0

ruddks1001 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말