글 읽기 - 답은 맞았는데 시간초과가 나요 ㅠㅠ

dhseo89 5년 전 0

DFS로 접근하여 풀었구요..

제 머릿속으로는 맞는거 같은데.. 시간초과가 나네요

고수님들 도와주세요 ㅜㅜ

import java.util.Scanner;

/*
2
2
0 0
1000 0
1000 1000
2000 1000
2
0 0
1000 500
2000 1000
2000 2000


1
2
0 0
10000 0
0 1000
0 2000
 */
public class Main {

	static int T;
	static int N;
	static int map[][];
	static int[] home = new int[2];
	static int[] festival = new int[2];
	static int[][] con;
	static final int BEER = 1000;
	static String result ="";
	static boolean[] visited;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		T = sc.nextInt();
		for (int i = 0; i < T; i++) {
			N = sc.nextInt();
			home[0] = sc.nextInt();
			home[1] = sc.nextInt();
			con = new int[N][2];
			visited = new boolean[N];
			for (int j = 0; j < N; j++) {
				con[j][0] = sc.nextInt();
				con[j][1] = sc.nextInt();
			}
			festival[0] = sc.nextInt();
			festival[1] = sc.nextInt();
			
			goFestival(home[0], home[1]);
			System.out.println(result.equals("") ? "sad": result);
			result = "";
		}
	}

	// 최대 갈 수 있는 거리 1000미터
	// x1-x2, y1-y2 총 가야할 거리
	// 현재위치에서 편의점까지 거리를 계산하고 1000이 넘으면 return
	private static void goFestival(int curX, int curY) {
		//System.out.println(curX+" "+curY);
		if (curX == festival[0] && curY == festival[1]) {
			return;
		} else {
			if(Math.abs(festival[0]-curX)+Math.abs(festival[1]-curY) <=BEER) { //차이가 1000이전일때는 그냥 리턴
				result = "happy";
				return;
			}
			else {
				for (int i = 0; i < con.length; i++) {
					int d = con[i][0] + con[i][1];
					int curD = curX + curY;
					if (Math.abs(curD - d) > BEER || visited[i]) continue;
						visited[i] = true;
						goFestival(con[i][0], con[i][1]);
						if(result.equals("happy")) return;
						visited[i] = false;
				}
			}
		}
	}
}

djm03178 5년 전 2

i번째 편의점을 방문한 후에, 끝까지 가는 데에 실패했다고 해서 다시 false로 만들 필요가 있을까요?

그리고 답도 틀립니다. 바로 아래 질문글을 읽어보신 것 같은데, 거기서 말하는 사항을 이 코드 역시 어기고 있습니다.

1
1
1000 0
0 1000
0 1001

정답: sad
출력: happy

dhseo89 5년 전 0

좀 더 꼼꼼히 살펴봐야겠네요

감사합니다

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

문제

문제

출처

ICPC

답은 맞았는데 시간초과가 나요 ㅠㅠ

dhseo89 5년 전 0

djm03178 5년 전 2

dhseo89 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말