글 읽기 - 두코드의 차이점을 모르겠습니다.

qkrqudwn12 7년 전 0

둘다 큐를 이용하고 순서를 이어가면서 붙이다 나중에 출력하는데 위 코드는 안되고 아래 코드는 되는

이유를 모르겠습니다.

//위코드-안됨
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class DSLR {
	static int start;
	static int end;
	static int d[] = new int[10001];
	static Queue<Point15> q = new LinkedList<Point15>();
	static final int INF = 987654321;

	public static void bfs(int start) {
		Arrays.fill(d, INF);
		q.add(new Point15(start, ""));
		d[start] = 0;
		while (!q.isEmpty()) {
			Point15 p = q.poll();
			int x = p.x;
			String str = p.str;
			if (x == end) {
				for (int i = str.length() - 1; i >= 0; i--) {
					System.out.print(str.charAt(i));
				}
				System.out.println();
				break;
			}
			int num = (x * 2) % 10000;

			if (d[num] > d[x] + 1) {
				d[num] = d[x] + 1;
				q.add(new Point15(num, str + "D"));
			}
			num = x - 1;
			if (num == -1)
				num = 9999;

			if (d[num] > d[x] + 1) {
				d[num] = d[x] + 1;
				q.add(new Point15(num, str + "S"));
			}

			num = x / 1000 + (x % 1000) * 10;

			if (d[num] > d[x] + 1) {
				d[num] = d[x] + 1;
				q.add(new Point15(num, str + "L"));
			}

			num = (x % 10) * 1000 + x / 10;

			if (d[num] > d[x] + 1) {
				d[num] = d[x] + 1;
				q.add(new Point15(num, str + "R"));
			}

		}
	}

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

		int testcase = scan.nextInt();
		while (testcase-- > 0) {
			start = scan.nextInt();
			end = scan.nextInt();
			bfs(start);
		}
	}
}

class Point15 {
	int x;
	String str;

	Point15(int x, String str) {
		this.x = x;
		this.str = str;
	}
}

//아래코드 -됨

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

public class DSLR2 {
	static int d[] = new int[10001];
	static int from[] = new int[10001];
	static char what[] = new char[10001];
	static boolean check[] = new boolean[10001];
	static Queue<Integer> q = new LinkedList<Integer>();

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int testcase = scan.nextInt();
		while (testcase-- > 0) {
			int start = scan.nextInt();
			int end = scan.nextInt();
			d[start] = 0;
			check[start] = true;
			q.add(start);
			while (!q.isEmpty()) {
				int x = q.poll();

				int num = (x * 2) % 10000;
				if (!check[num]) {
					check[num] = true;
					d[num] = d[x] + 1;
					from[num] = x;
					q.add(num);
					what[num] = 'D';
				}
				num = x - 1;
				if (num == -1)
					num = 9999;
				if (!check[num]) {
					check[num] = true;
					d[num] = d[x] + 1;
					from[num] = x;
					q.add(num);
					what[num] = 'S';
				}
				num = x / 1000 + (x % 1000) * 10;
				if (!check[num]) {
					check[num] = true;
					d[num] = d[x] + 1;
					from[num] = x;
					q.add(num);
					what[num] = 'L';
				}
				num = (x % 10) * 1000 + x / 10;
				if (!check[num]) {
					check[num] = true;
					d[num] = d[x] + 1;
					from[num] = x;
					q.add(num);
					what[num] = 'R';
				}
			}
			String ans = "";
			while (true) {
				ans += what[end];
				end = from[end];
				if (end == start)
					break;
			}
			for (int i = ans.length() - 1; i >= 0; i--)
				System.out.print(ans.charAt(i));
			System.out.println();
			Arrays.fill(d, 0);
			Arrays.fill(check, false);
			Arrays.fill(from, 0);

		}
	}
}

tyburn117 7년 전 0

거꾸로 출력해보세요

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

문제

문제

출처

ICPC

두코드의 차이점을 모르겠습니다.

qkrqudwn12 7년 전 0

tyburn117 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말