글 읽기 - 17%에서 시간초과가 발생합니다. (주석)

jrw9215 2년 전 0

노드클래스의 멤버필드 y,x는 각각 y, x좌표를

c는 걸린 시간, k는 벽을 부술 수 있는 횟수의 잔여량

d는 0이면 현재 노드가 낮의 상태를, 1이면 밤의 상태를 가짐을 나타냅니다.

visit배열은 4차원으로 선언했으며, visit[y][x][k][d]와 같이 접근할 수 있습니다.

전체적으로 동작을 설명하자면

1- 조건에 따라 상하좌우 4방향 및 정지해있을때의 상태를 큐에 추가합니다.

2- 만약 상하좌우로 탐색했을때 그 위치에 벽이 있고, 현재 낮이며, 벽을 부술수 있는 횟수가 남아있고

벽을 부수고 나서 반나절의 시간이 걸려 그곳에 도착한 적이 없었다면

벽 파괴 남은 횟수를 1 감소시키고, 걸린 시간은 증가시키며

nd = (n.d+1)%2와 같이 현재 낮(0)이면 밤(1)으로, 현재 밤이면 낮으로 변경되도록 설정된 변수를 사용해

그곳에 방문했음을 처리합니다.

3- 상하좌우 탐색시 그곳에 벽이 없고 반나절이 걸려 그곳에 도착한 적이 없었다면

방문했음을 처리합니다.

4- 상하좌우 탐색을 마치고, 현재 밤이고, 그곳에 반나절 머무른 적이 없으면

다시 한번 그 자리에 머무르도록 처리합니다.

로직자체는 얼추 맞는 것 같으나, 17%에서 시간초과가 발생합니다.

아무래도 방문배열이 4차원이여서라기 보다는, 제자리에 머무는 처리와 관련해서

문제가 있는 것 같은데, 정확한 원인은 잘 모르겠습니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;

class Node{
	//y,x는 좌표
	//c는 걸린 시간
	//k는 벽을 부술 수 있는 벽 파괴가능 잔여 횟수
	//d는 0이면 현재 상태가 낮, 1이면 밤을 의미함
	int y, x, c, k, d;
	Node(int y, int x, int c, int k, int d){
		this.y = y;
		this.x = x;
		this.c = c;
		this.k = k;
		this.d = d;
	}
}

public class Main {
	public static int N;
	public static int M;
	public static int K;
	public static boolean[][][][] visit;
	
	//true일때는 길, false일때는 벽을 의미함
	public static boolean[][] map;
	
	public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	
	public static void BFS() throws Exception{
		int[][] dist = {{-1,0},{1,0},{0,-1},{0,1}};
		Queue<Node> q = new LinkedList<Node>();
		
		//벽을 부술 수 있는 횟수 K가 1이상이어야만 벽을 부술 수 있음
		q.add(new Node(0,0,1,K,0));
		visit[0][0][K][0] = true;
		
		while(!q.isEmpty()) {
			Node n = q.poll();
			
			int nd = (n.d+1)%2;
			
			//목적지에 도착하면 탐색을 종료
			if(n.y==N-1&&n.x==M-1) {
				bw.write(n.c+"\n");
				bw.flush();
				return;
			}
			
			for(int i=0; i<dist.length; i++) {
				
				int y = n.y + dist[i][0];
				int x = n.x + dist[i][1];
				
				//인덱스가 맵 범위를 벗어나지 않을때
				if(y>=0&&y<N&&x>=0&&x<M) {
					
					//그 위치에 벽이 있고, 부술 수 있는 횟수가 남아있으며, 낮이고
					//아직 벽을 부순후 그곳에 도착한 적이 없었을때
					if(!map[y][x]&&n.k>0&&n.d==0&&!visit[y][x][n.k-1][1]) {
						
						//벽파괴 가능 잔여 횟수를 1감소시키고
						//거리를 1 증가시키며, 현재 상태 d를 밤을 뜻하는 1로 설정
						q.add(new Node(y,x,n.c+1,n.k-1,1));
						visit[y][x][n.k-1][1] = true;
					}
		
					//그 위치에 벽이 없고, 그곳에 도착한 적이 없으면
					//해당 위치를 방문함
					//현재 낮이라면 nd는 밤을 의미하는 1을
					//현재 밤이라면 nd는 낮을 의미하는 0을 가지며
					//낮이든 밤이든 반나절이 걸려 그곳에 도착한 적이 없다면
					//방문하는 것으로 처리함
					if(map[y][x]&&!visit[y][x][n.k][nd]) {
						q.add(new Node(y,x,n.c+1,n.k,nd));
						visit[y][x][n.k][nd] = true;
					}
				}
			}
			
			//현재 밤이고 지금의 위치에서 반나절을 기다린 적이 없었다면
			//해당 위치에서 반나절을 기다림
			if(n.d==1&&!visit[n.y][n.x][n.k][nd]) {
				q.add(new Node(n.y,n.x,n.c+1,n.k,nd));
				visit[n.y][n.x][n.k][nd] = true;
			}
		}
		bw.write("-1\n");
		bw.flush();
	}
	
	public static void main(String[] args) throws Exception{
		String[] temp = br.readLine().split(" ");
		
		N = Integer.parseInt(temp[0]);
		M = Integer.parseInt(temp[1]);
		K = Integer.parseInt(temp[2]);

		visit = new boolean[N][M][K+1][2];
		map = new boolean[N][M];
		
		for(int i=0; i<N;i++) {
			temp = br.readLine().split("");
			for(int j=0; j<M; j++) {
				if(temp[j].equals("0")) {
					map[i][j] = true;
				}
			}
		}

		BFS();
	}
}

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

문제

문제

출처

ICPC

17%에서 시간초과가 발생합니다. (주석)

jrw9215 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말