글 읽기 - 시간초과 관련하여 질문드립니다..

ghysnzsy 3년 전 0

테스트케이스를 구해서 전체 정답을 맞아내긴 했습니다...

먼저 불을 queueF에 집어넣은 후, 각각에 대한 BFS를 돌려 바닥에 불이 생성되는 시간을 구해준 뒤에

queueM의 사람을 이용해서 각 바닥이 0이거나 현재 자신이 있는 위치의 시간+1이 해당 바닥의 불이 생성된 시간보다 작은 경우에 이동을 하도록 구현을 했습니다.

초기화를 하는 것도 문제가 되나 싶어서 visited, visited2, line, line2로 쪼개보았는데요..

기본적인 queue와 BFS의 규칙은 맞게 사용한 듯 한데 어떤 점이 부족했는지 모르겠습니다.. 이틀째 보고 있는데 정말 슬프네요...

import java.util.*;

class Node {
	public boolean visited = false;
	public boolean visited2 = false;
	public int n;
	public int ch = 0;
	public List<Integer> line = new ArrayList<>();
	public List<Integer> line2 = new ArrayList<>();
	public Node(int n) {
		this.n = n;
	}
	
	public List<Integer> searchBFS(List<Node> nodeList) {
		List<Integer> result = new ArrayList<>();
		visited = true;
		for(int i = 0; i<line.size();++i) {
			nodeList.get(line.get(i)).line.remove(nodeList.get(line.get(i)).line.indexOf(n));
			if(nodeList.get(line.get(i)).visited == false && nodeList.get(line.get(i)).ch == 0) {
				result.add(line.get(i));
				nodeList.get(line.get(i)).visited =true;
				nodeList.get(line.get(i)).ch = ch+1;
			}
		}
		return result;
	}
	public List<Integer> searchBFSM(List<Node> nodeList) {
		List<Integer> result = new ArrayList<>();
		visited2 = true;
		for(int i = 0; i<line2.size();++i) {
			if(nodeList.get(line2.get(i)).visited2 == false && (nodeList.get(line2.get(i)).ch > ch+1|| nodeList.get(line2.get(i)).ch == 0)) {
				result.add(line2.get(i));
				nodeList.get(line2.get(i)).visited2 =true;
				nodeList.get(line2.get(i)).ch = ch+1;
			}
		}
		return result;
	}
}

public class Main {

    public static void main(String[] args) {
    	
        Scanner scanner = new Scanner(System.in);
        
        int n = scanner.nextInt();
        for(int i = 0; i<n;++i) {
        	
        	int y = scanner.nextInt();
        	int x = scanner.nextInt();
        	scanner.nextLine();
        	List<Integer> goalList = new ArrayList<>();
        	List<Node> nodeList = new ArrayList<>();
        	Queue<Integer> queueF = new LinkedList<>();
        	Queue<Integer> queueM = new LinkedList<>();
        	
        	for(int j = 0; j<x;++j) {
        		String s = scanner.nextLine();
        		for(int k = 0; k<y; ++k) {
        			int val = j*y+k;
        			nodeList.add(new Node(val));
        			
        			String sub = s.substring(0+k, 1+k);
        			if(sub.equals("#")) {
        				nodeList.get(val).ch = -1;
        				
        			}
        			else {
        				if(j > 0 && nodeList.get(val-y).ch == 0) {
        					nodeList.get(val).line.add(val-y);
        					nodeList.get(val-y).line.add(val);
        					nodeList.get(val).line2.add(val-y);
        					nodeList.get(val-y).line2.add(val);
        				}
        				if(k > 0 && nodeList.get(val-1).ch == 0) {
        					nodeList.get(val).line.add(val-1);
        					nodeList.get(val-1).line.add(val);
        					nodeList.get(val).line2.add(val-1);
        					nodeList.get(val-1).line2.add(val);
        				}	
        				if(sub.equals("@")) {
            				queueM.add(val);
            			}
    					else if(sub.equals("*")) {
    						nodeList.get(val).visited = true;
            				nodeList.get(val).ch = 1;
            				queueF.add(val);
            			}
        				if((k == 0 || k == y-1 || j == 0 || j == x-1) && nodeList.get(val).ch == 0) {
        					goalList.add(val);
        				}
        			}
        		}
        	}
        	while(!queueF.isEmpty()) {
        		int val = queueF.poll();
        		queueF.addAll(nodeList.get(val).searchBFS(nodeList));
        	}
        	boolean result = false;
        	
        	nodeList.get(queueM.peek()).ch = 1;
        	while(!queueM.isEmpty()) {
        		int val = queueM.poll();

        		if(goalList.indexOf(val) > -1) {
        			result = true;
        			System.out.println(nodeList.get(val).ch);
        			break;
        		}
        		queueM.addAll(nodeList.get(val).searchBFSM(nodeList));
        	}

        	if(!result)
        		System.out.println("IMPOSSIBLE");
        }
        return;
    }
}

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

문제

문제

출처

ICPC

시간초과 관련하여 질문드립니다..

ghysnzsy 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말