글 읽기 - 시간초과 관련 질문입니다

baegyu3 4년 전 0

채점 0%에서 계속 시간초과가 나서 질문올립니다.

빈칸 검사를 2차원배열 체크에서 변수로 바꾸고,

백트래킹도 전체루프 방식으로 하다가 리스트에 바이러스 위치를 담아 중복 없이 탐색하게 바꿨습니다.

예제는 모두 잘 출력되는데 0%에서 채점 진행이 안되는거면 뭔가 실수가 있는것 같습니다.

혹시 이상한 부분이 있다면 알려주시면 감사하겠습니다!

import java.io.*;
import java.util.*;

public class Main {
    
    static int n;
    static int m;
    static int a[][];
    static ArrayList<Pair> virus = new ArrayList<Pair>();
    static int dx[] = {-1, 1, 0, 0};
    static int dy[] = {0, 0, -1, 1};
    static int min = Integer.MAX_VALUE;
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        a = new int[n][n];
        
        for(int i=0; i<n; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<n; j++) {
                a[i][j] = Integer.parseInt(st.nextToken());
                if(a[i][j] == 2) virus.add(new Pair(i, j));
            }
        }
        
        setVirus(0, 0);
        
        System.out.println(min == Integer.MAX_VALUE ? -1 : min);
    }
    
    public static void setVirus(int idx, int cnt) {
        if(cnt == m) {
            bfs();
            return;
        }
        
        if(idx == virus.size()) return;
        
        for(int i=idx; i<virus.size(); i++) {
            Pair p = virus.get(i);
            a[p.x][p.y] = 3;
            setVirus(idx+1, cnt+1);
            a[p.x][p.y] = 2;
        }
    }
    
    /* 0 : 빈칸
     * 1 : 벽
     * 2 : 비활성 바이러스
     * 3 : 활성 바이러스
     */
    public static void bfs() {
        Queue<Pair> q = new LinkedList<Pair>();
        int temp[][] = new int[n][n];
        boolean visited[][] = new boolean[n][n];
        int empty = 0;
        
        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++) {
                temp[i][j] = a[i][j];
                if(a[i][j] == 3) {
                    q.offer(new Pair(i, j));
                    visited[i][j] = true;
                }
                if(a[i][j] == 0) empty++;
            }
        
        int t = 0;
        while(!q.isEmpty()) {
            int size = q.size();
            
            if(min <= t) return; //가지치기
            if(empty == 0) break; //빈칸이 없으면 탐색 중지
            
            while(size-->0) {
                Pair p = q.poll();
                for(int i=0; i<4; i++) {
                    int nx = p.x + dx[i];
                    int ny = p.y + dy[i];
                    if(0 <= nx && nx < n && 0 <= ny && ny < n) {
                        if(!visited[nx][ny] && temp[nx][ny] != 1) {
                            if(temp[nx][ny] == 0) empty--;
                            visited[nx][ny] = true;
                            temp[nx][ny] = 3;
                            q.offer(new Pair(nx, ny));
                        }
                    }
                }
            }
            t++;
        }
        
        if(empty == 0) min = Math.min(min, t);
    }
    
    static class Pair {
        int x;
        int y;
        
        Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

baegyu3 4년 전 3

백트래킹 과정에서

setVirus(idx+1, cnt+1);

을

setVirus(i+1, cnt+1);

로 바꿔 해결했습니다.

qjemfrkwl23 4년 전 1

감사합니다.. 저도 같은 실수했네요 ㅠㅠ

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

문제

문제

출처

ICPC

시간초과 관련 질문입니다

baegyu3 4년 전 0

baegyu3 4년 전 3

qjemfrkwl23 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말