글 읽기 - 안녕하세요, 접근을 어떻게 해야할지 모르겠습니다..

hanjh04 6년 전 0

어떤식으로 접근해야할지 몰라서 일단 무식하게 한 칸씩 검사하며 이동하는 방식으로 구현했습니다..(예제를 많이 그려봤는데, 입력받은 처음과 끝 좌표의 거리가 짝수이면 경로를 만들 수 없어서 바로 -1을 출력하도록 했습니다.)

8*8까지 돌려본 결과 시간은 많 걸리지만 경로는 오류 없이 출력이 되는 것 같은데 채점을 해보면 시간초과가 아닌 틀렸다고 나옵니다.

어느부분이 틀린걸까요??

그리고 어떻게 하면 수행 시간을 단축시킬 수 있을까요?? 힌트좀 주시면 감사하겠습니다!!!!!

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.StringTokenizer;

public class Main {
	static int T;
	static int R, C, r1, r2, c2, c1;
	static int[] dr = { -1, 0, 1, 0 };
	static int[] dc = { 0, 1, 0, -1 };
	static boolean[][] visited;

	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		T = Integer.parseInt(br.readLine());

		for (int i = 0; i < T; i++) {
			st = new StringTokenizer(br.readLine());
			R = Integer.parseInt(st.nextToken());
			C = Integer.parseInt(st.nextToken());
			visited = new boolean[R + 1][C + 1];
			st = new StringTokenizer(br.readLine());
			r1 = Integer.parseInt(st.nextToken());
			c1 = Integer.parseInt(st.nextToken());
			st = new StringTokenizer(br.readLine());
			r2 = Integer.parseInt(st.nextToken());
			c2 = Integer.parseInt(st.nextToken());
			visited[r1][c1] = true;
			if ((Math.abs(r1 - r2) + Math.abs(c1 - c2)) % 2 == 0) {
				System.out.println(-1);
				continue;
			}
			//Long l = System.currentTimeMillis();
			if (dfs(r1, c1, 1, false)) {
				System.out.println(1);
			}
			//System.out.println(System.currentTimeMillis() - l);
		}
	}

	public static boolean canMove(int r, int c) {
		if (r >= 1 && r <= R && c >= 1 && c <= C && !visited[r][c]) {
			return true;
		}
		return false;
	}

	public static boolean dfs(int r1, int c1, int count, boolean ff) {
		if (r1 == r2 && c1 == c2) {
			if (count == R * C) {
				System.out.println(1);
				System.out.println(r1 + " " + c1);
				ff = true;
			}
			return ff;
		}
		int a, b;
		if (count < R * C && (r1 != r2 || c1 != c2)) {
			for (int i = 0; i < 4; i++) {
				a = r1 + dr[i];
				b = c1 + dc[i];
				if (canMove(a, b)) {
					// if (a >= 1 && a <= R && b >= 1 && b <= C &&
					// !visited[a][b]) {
					visited[a][b] = true;
					if (ff = dfs(a, b, count + 1, ff)) {
						System.out.println(r1 + " " + c1);
						return ff;
					}
					visited[a][b] = false;
				}
			}
		}
		return ff;
	}
}

zlzmsrhak 6년 전 1

이 문제는 시간을 효율적으로 줄이는 것이 목표인 문제이고, 그만큼 어렵습니다..

단순히 이동만 한다면 엄청나게 많은 경우의 수(3^20을 아득히 넘어가는)가 나오기 때문에 알고리즘을 잘 만들어야 합니다.

만약 이 문제를 단순한 백트래킹을 연습하기 위해 풀고 있으시다면, 다른 문제를 푸는 것을 추천드립니다.

hanjh04 6년 전 0

넵ㅎㅎ 다른 문제 좀 풀다가 나중에 다시 풀어봐야겠어요

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

문제

문제

출처

ICPC

안녕하세요, 접근을 어떻게 해야할지 모르겠습니다..

hanjh04 6년 전 0

zlzmsrhak 6년 전 1

hanjh04 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말