글 읽기 - 자바 시간초과 해결해주실 수 있나요?

ssyup4259 5년 전 1

BFS로 구현을 했습니다.

정답들은 잘 나오지만 결국 시간초과가 나네요.

혹시 왜 시간초과가 나는지 알 수 있나요?

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Ex17070 {
	static int N;
	static int[][] map;
	// 우, 우하, 하 3방향
	static int[][] dir = { { 0, 1 }, { 1, 1 }, { 1, 0 } };
	static int result;

	static class Info {
		int r, c, dir; // 파이프의 앞쪽 좌표, 방향

		Info(int r, int c, int dir) {
			this.r = r;
			this.c = c;
			this.dir = dir;
		}
	}

	static boolean isRange(int r, int c) {
		if (r <= 0 || r > N || c <= 0 || c > N) {
			return false;
		}
		return true;
	}

	static void bfs(int r, int c) {
		Queue<Info> que = new LinkedList<>();
		que.add(new Info(r, c, 0));

		while (!que.isEmpty()) {
			int nowR = que.peek().r;
			int nowC = que.peek().c;
			int nowD = que.poll().dir;

			if (nowR == N && nowC == N) {
				result++;
				continue;
			}
			
			//지금 현재 아래방향이 아니고 오른쪽이 범위내이고 벽이아니라면
			if (nowD != 2 && isRange(nowR, nowC + 1) && map[nowR][nowC + 1] == 0) {
				que.add(new Info(nowR, nowC + 1, 0));
			}
			if (nowD != 0 && isRange(nowR + 1, nowC) && map[nowR + 1][nowC] == 0) {
				que.add(new Info(nowR + 1, nowC, 2));
			}
			if (isRange(nowR + 1, nowC + 1) && map[nowR + 1][nowC] == 0 && map[nowR + 1][nowC + 1] == 0
					&& map[nowR][nowC+1] == 0) {
				que.add(new Info(nowR + 1, nowC + 1, 1));
			}
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		map = new int[N + 1][N + 1];
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				map[i][j] = sc.nextInt();
			}
		}
		result = 0;
		bfs(1, 2);
		System.out.println(result);
	}
}

startlink 5년 전 0

BFS로 구현한 것 같지만, 브루트 포스입니다.

https://www.acmicpc.net/board/...

ssyup4259 5년 전 0

감사합니다.

저 글은 질문 올리기전에 봤었습니다.

근데 같은 접점을 또 방문하게 된다고 말씀하셨는데

간단한예를들어

우 우 하 방향으로 오는 것과

하 우 우 방향으로 오는 것이 같은 접점을 또 방문하게 된다는 의미 인가요?

startlink 5년 전 0

네

그리고 접점이 아니고 정점입니다

개선하려면 우하우랑 하우우를 같은 것으로 쳐줘야 합니다

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

문제

문제

출처

ICPC

자바 시간초과 해결해주실 수 있나요?

ssyup4259 5년 전 1

startlink 5년 전 0

ssyup4259 5년 전 0

startlink 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말