글 읽기 - 시간초과11%

syoungee 4년 전 0

11%에서 시간 초과가 나는데 효율성을 높일 수 있는 방법이 있을까요?

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

class Pos {
	int x;
	int y;

	public Pos(int x, int y) {
		this.x = x;
		this.y = y;
	}
}

public class Main {
	public static int H; // 가로, 세로
	public static int W;
	public static int graph[][];
	public static int temp[][];
	public static LinkedList<Pos> list = new LinkedList<Pos>();
	public static int dx[] = { 0, 0, 1, -1, 1, -1, 1, -1 };
	public static int dy[] = { 1, -1, 0, 0, 1, 1, -1, -1 };
	public static boolean flag = false;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String tem = br.readLine();
		String str[] = tem.split(" ");
		H = Integer.parseInt(str[0]);
		W = Integer.parseInt(str[1]);

		graph = new int[H][W];
		temp = new int[H][W];
		for (int i = 0; i < H; i++) {
			tem = br.readLine();
			for (int j = 0; j < W; j++) {
				if (tem.charAt(j) != '.') {
					graph[i][j] = Integer.parseInt(tem.substring(j, j + 1));
					if (graph[i][j] != 0)
						list.addLast(new Pos(i, j));
				}
			}
		}
 
		int answer = 0;
		while (true) {
			answer++;
			flag = false;
			while (!list.isEmpty()) {
				Pos now = list.pollFirst();
				int sum = 0;
				for (int d = 0; d < 8; d++) {
					int nx = now.x + dx[d];
					int ny = now.y + dy[d];
					if (nx < 0 || nx >= H || ny < 0 || ny >= W) {
						continue;
					}
					if (graph[nx][ny] == 0) {
						sum++;
					}
				}
				temp[now.x][now.y] = sum;
			}

			for (int i = 0; i < H; i++) {
				for (int j = 0; j < W; j++) {
					if (graph[i][j] == 0)
						continue;
					if (graph[i][j] <= temp[i][j]) {
						flag = true;
						graph[i][j] = 0;
						continue;
					}
					list.addLast(new Pos(i, j));
				}
			}

			temp = new int[H][W];
			
			if (!flag) {
				System.out.println(answer - 1);
				return;
			}
		}

	}

}// main 종료

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

문제

문제

출처

ICPC

시간초과11%

syoungee 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말