글 읽기 - 시간초과 질문드립니다..

leeking91 6년 전 0

처음에 답은 제대로 나와서 , 돌렸는데 시간초과가 나왔습니다

그래서 visit[][] 추가했는데 이번엔 2가 나오더군요 ;

답은 : 3<<

메모제이션으로 바꿔야될것같은데 어느 부분에서 어떻게 바꾸는 것이 좋을까요 ? ..

감이 안오네요 ..

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

public class Boj1520dp {

	public static int n, m, cnt = 0;
	public static int[][] map;
	public static boolean[][] visit;
	public static int[] dx = { 0, 0, 1, -1 };
	public static int[] dy = { 1, -1, 0, 0 };
	public static Scanner in = new Scanner(System.in);

	public static void main(String args[]) {
		n = in.nextInt();
		m = in.nextInt();
		map = new int[n][m];
		visit = new boolean[n][m];
		System.out.println(dp());
	}

	public static boolean isRange(int nx, int ny) {

		return (nx < n && ny < m && nx >= 0 && ny >= 0);

	}

	public static boolean canMove(int nx, int ny, int x, int y) {
		return (map[nx][ny] < map[x][y]);
	}

	public static int dp() {
		init();

		Queue<Node> q = new LinkedList<>();

		q.add(new Node(0, 0));

		while (!q.isEmpty()) {
			Node node = q.poll();
			visit[node.x][node.y] = true;
			for (int i = 0; i < 4; i++) {
			
				int nx = node.x + dx[i];
				int ny = node.y + dy[i];
				System.out.println(nx + " : " + ny);
				if (isRange(nx, ny) && canMove(nx, ny, node.x, node.y)&&visit[nx][ny]==false) {

					if (nx == n-1 && ny == m-1) {
						cnt++;
					}
					q.add(new Node(nx, ny));

				}
			}
		}

		return cnt;
	}

	public static void init() {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				map[i][j] = in.nextInt();
				visit[i][j] = false;
			}
		}
	}

	static class Node {
		int x;
		int y;

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

	}

}

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

문제

문제

출처

ICPC

시간초과 질문드립니다..

leeking91 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말